当前位置：首页 > news >正文

动态规划实战：从硬币找零到最优解算法设计

news 2026/5/31 22:46:09

1. 从零理解动态规划：为什么硬币找零是个好例子

第一次听说动态规划时，我和大多数人一样懵——这名字听起来既抽象又吓人。直到遇到硬币找零问题，才真正明白它的精妙。想象你站在便利店收银台前，钱包里有1元、2元和5元硬币，现在要给顾客找零11元，怎么搭配才能用最少的硬币数？这就是动态规划的完美入门案例。

硬币问题之所以经典，是因为它同时具备三个关键特征：最优子结构（大问题的最优解包含小问题的最优解）、重叠子问题（计算过程中会反复遇到相同的小问题）和无后效性（当前决策不影响之前的状态）。比如要计算凑11元的最优解，必须先知道凑10元、6元和9元的最优解——这些子问题会像俄罗斯套娃一样不断嵌套出现。

我刚开始尝试用递归暴力破解时，发现当金额超过30元程序就卡死了。后来用动态规划重写，同样的计算瞬间完成。这个性能差距让我意识到：动态规划本质上是用空间换时间的艺术。它通过一个数组记住所有中间结果，避免重复计算，把指数级复杂度降到了多项式级别。

2. 拆解动态规划四步法：以硬币问题为例

2.1 定义状态：设计你的记忆容器

状态定义是动态规划最关键的步骤。对于硬币问题，我们创建dp数组，其中dp[i]表示凑出金额i需要的最少硬币数。这个定义看似简单，却是我踩过最多坑的地方——最初错误地定义dp[i][j]表示前i种硬币凑j元，结果把问题复杂化了。

实际编码时要注意数组大小。比如目标金额是n，数组长度应该是n+1，因为要考虑从0元到n元的所有情况。Java中初始化可以这样写：

int[] dp = new int[amount + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; // 基准情况

2.2 状态转移：寻找数学规律

状态转移方程是动态规划的灵魂。对于硬币问题，核心思路是：对于每个金额i，尝试所有可能的硬币coin，如果i-coin这个金额可达，那么dp[i]可能就是dp[i-coin]+1。用数学表达就是：

dp[i] = min(dp[i], dp[i - coin] + 1) 对所有coin∈coins

这个方程我花了三天才真正理解。后来发现用具体数字举例就容易多了：假设硬币有[1,2,5]，要凑11元。当i=11时，我们比较：

用5元硬币：需要dp[6]+1
用2元硬币：需要dp[9]+1
用1元硬币：需要dp[10]+1 取这三个结果的最小值就是最终解。

2.3 初始化：设置好起点

初始化常常被忽视，但却决定算法正确性。dp[0]=0这个基准条件表示"凑0元需要0个硬币"，看似废话，但如果没有它，整个算法就无法启动。其他位置初始化为无穷大（或一个足够大的数），表示"暂时无法凑出"。

在项目中曾遇到一个bug：有人把dp[0]初始化为1，导致所有结果多算一个硬币。这个错误提醒我们：基准情况必须严格符合物理意义。

2.4 遍历顺序：细节决定成败

硬币问题的遍历顺序有两种选择：

外层遍历金额，内层遍历硬币
外层遍历硬币，内层遍历金额

第一种方式更直观但效率较低，第二种才是标准做法。因为按硬币遍历可以更好地利用之前计算的结果，也更容易处理某些边界条件。具体实现如下：

for (int coin : coins) { for (int i = coin; i <= amount; i++) { if (dp[i - coin] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } }

3. 从理论到实践：完整代码实现与优化

3.1 基础版本实现

完整的Java实现应该包含以下要素：

public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int coin : coins) { for (int i = coin; i <= amount; i++) { if (dp[i - coin] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; }

这段代码有几个易错点：

数组越界：当coin比amount大时，内层循环不会执行
整数溢出：如果用Integer.MAX_VALUE+1会变成负数
返回值处理：无法凑出时应返回-1而非MAX_VALUE

3.2 空间优化技巧

虽然标准解法空间复杂度已经是O(n)，但在某些场景还能优化。如果硬币面值有规律（比如全是1的倍数），可以用滚动数组进一步减少空间使用。更实用的优化是提前对硬币排序：

Arrays.sort(coins); // 升序排列 for (int i = 0; i < coins.length && coins[i] <= amount; i++) { // 内层循环 }

这样当硬币面值超过当前金额时可以直接跳过，减少不必要的计算。

3.3 打印具体方案

有时我们不仅需要硬币数量，还需要知道具体组合。可以增加一个prev数组记录路径：

int[] prev = new int[amount + 1]; Arrays.fill(prev, -1); // 在更新dp时记录 if (dp[i - coin] + 1 < dp[i]) { dp[i] = dp[i - coin] + 1; prev[i] = coin; } // 回溯输出方案 List<Integer> res = new ArrayList<>(); int curr = amount; while (curr > 0 && prev[curr] != -1) { res.add(prev[curr]); curr -= prev[curr]; }