有面额为 1、3、4 的硬币,每种都可以使用任意多枚。要恰好凑出金额 6,最少需要几枚?
每次尽量选择大面额,会得到 4 + 1 + 1,共三枚。但 3 + 3 只要两枚。这个例子说明:当前看起来最划算的一步,未必能组成整体最好的方案。
本篇用这个问题学习动态规划:把原问题拆成可以复用的子问题,保存每个子问题的结果,再按依赖顺序求出最终答案。示例使用 Java 17 及以上版本。系列目录也列出了前面关于数组、递归和回溯的文章。
一、先明确这道题允许做什么
输入包含面额数组 coins 和目标金额 amount。所有面额必须是正整数,每种硬币可以重复使用。目标是恰好凑出金额的最少硬币数量。
coins = [1, 3, 4], amount = 6 → 2coins = [2], amount = 3 → -1coins = [1, 3, 4], amount = 0 → 0-1 表示无法凑出;目标为零时,什么都不拿即可,需要零枚硬币。
这里求的是最少数量,没有要求列出使用了哪些硬币,也没有要求统计所有方案数。把问题说清楚,后面才知道数组里应该保存什么。
硬币如果每种只能使用一次,就变成另一道题。本文的转移允许继续使用相同面额,不能直接用于“每枚硬币只能使用一次”的场景。
二、从“最后一枚是什么”开始拆问题
假设我们已经找到了凑出 6 的最优方案。它的最后一枚可能是 1、3 或 4。
- 最后一枚是 1,前面必须先凑出 5。
- 最后一枚是 3,前面必须先凑出 3。
- 最后一枚是 4,前面必须先凑出 2。
如果凑出这些较小金额的最少数量已经知道,只需要分别加上一枚,再选出最小值。
于是定义:
dp[a]:恰好凑出金额 a 所需的最少硬币数量例如 dp[3] = 1,因为直接拿一枚面额 3 的硬币即可。最终要求的答案就是 dp[amount]。
这里还隐含了一个理由:最优方案去掉最后一枚后,剩下的部分也应该是对应金额的最优方案。否则,把剩下的部分换成更少硬币的方案,就能得到一个更好的完整方案,与原先的“最优”矛盾。
这种性质通常称为最优子结构。学习时先理解这段替换理由,再记术语。
三、写出转移、初值和计算顺序
对于金额 a,枚举最后一枚硬币 coin。只有 coin <= a,并且 a - coin 可以凑出,才形成一个合法候选:
候选数量 = dp[a - coin] + 1dp[a] = 所有合法候选数量中的最小值这就是状态转移。它把当前状态与更小的状态联系起来。
初值只有一个确定答案:dp[0] = 0。其他金额暂时未知,应标记为不可达,不能把它们也默认当作零。
因为所有面额都大于零,所以 a - coin < a。只要按照金额 1、2、3……amount 的顺序计算,当前状态需要的较小状态就已经准备好。
现在可以在纸上完成 [1, 3, 4]、目标 6 的计算:
| 金额 a | 可选的最后一枚及候选数量 | dp[a] |
|---|---|---|
| 0 | 不用硬币 | 0 |
| 1 | 1:dp[0] + 1 = 1 | 1 |
| 2 | 1:dp[1] + 1 = 2 | 2 |
| 3 | 1:3 枚;3:1 枚 | 1 |
| 4 | 1:2 枚;3:2 枚;4:1 枚 | 1 |
| 5 | 1:2 枚;3:3 枚;4:2 枚 | 2 |
| 6 | 1:3 枚;3:2 枚;4:3 枚 | 2 |
最后得到:
金额:0 1 2 3 4 5 6数量:0 1 2 1 1 2 2同一个小金额的结果可能被多个大金额使用。例如 dp[3] 会参与计算 4、6 等状态,但它本身只计算一次。这正是保存子问题结果带来的收益。
四、让“不可达”有一个明确的表示
Java 的 int[] 默认全是零。如果不处理初值,计算 dp[a - coin] + 1 时就可能把一个根本凑不出的金额当作零枚硬币。
本例使用 amount + 1 作为不可达标记。为什么这个值安全?
硬币面额都是正整数,最小也至少为 1。因此,任何能凑出金额 a 的方案都不会使用超过 a 枚硬币。所有有效数量都不超过 amount,所以 amount + 1 不会与合法答案混淆。
教学实现把目标金额限制在 0~100000,控制状态数组的大小,也让这个标记的加法处在安全范围内。这是示例的资源约束,和动态规划思想本身的适用范围要分开理解。
五、把推导直接翻译成 Java
下面是完整示例的常量和核心方法,省略 CoinChange 类以及 java.util.Arrays 的导入:
public static final int MAX_AMOUNT = 100_000;
public static int minCoins(int[] coins, int amount) { if (coins == null || amount < 0 || amount > MAX_AMOUNT) { throw new IllegalArgumentException("coins required; amount must be 0..100000"); } for (int coin : coins) { if (coin <= 0) { throw new IllegalArgumentException("coin values must be positive"); } } int unreachable = amount + 1; int[] dp = new int[amount + 1]; Arrays.fill(dp, unreachable); dp[0] = 0; for (int value = 1; value <= amount; value++) { for (int coin : coins) { if (coin <= value && dp[value - coin] != unreachable) { dp[value] = Math.min(dp[value], dp[value - coin] + 1); } } } return dp[amount] == unreachable ? -1 : dp[amount];}外层循环确定“现在计算哪个金额”,内层循环枚举“最后一枚可以是什么”。Math.min 保留目前发现的最好结果。
检查 dp[value - coin] != unreachable,是为了只从真正能到达的状态继续计算。面额为零或负数则直接拒绝:零面额不能减小子问题,负面额还会破坏数组下标和计算顺序的前提。
面额不必排序。重复面额只会造成重复计算同一个候选,不会改变最少数量;输入为空数组时,金额零返回 0,正金额返回 -1。
六、运行后验证哪些情况
下载完整 CoinChange.java,或者下载系列源码包。在文件所在目录运行:
javac -encoding UTF-8 CoinChange.javajava CoinChange预期输出:
2-10三行分别覆盖普通可达情况、无法凑出的金额和零金额。继续验证 [2, 5] 凑 10,应得到 2;[4, 6] 凑 7,应得到 -1。
如果把 Arrays.fill 删除,再运行无法凑出的测试,就能看到初值错误怎样影响结果。理解这种失败,比只记住“数组要初始化”更容易迁移到其他题目。
非法参数有另一种处理方式:目标金额为负数或超过上限、出现非正面额、数组为 null,都会抛出 IllegalArgumentException,与“输入合法但无法凑出”的 -1 区分。
七、动态规划省掉了什么,又花掉了什么
设目标金额为 A,面额数组的长度为 k。在 A ≥ 1、k ≥ 1 时,需要计算 A 个金额,每个金额最多检查 k 个面额,时间复杂度是 O(A × k);状态数组占用 O(A) 空间。数组中若有重复面额,重复项也计入这里的 k。
这里成本随着金额的数值增长。把金额从一万增加到十亿,即使输入文本只多几个数字,状态数量也会大幅增加。不能仅凭“用了动态规划”就认为处理任何大金额都很快。
如果只用递归枚举拿哪一枚,可能反复计算相同的剩余金额。记忆化搜索是在递归时缓存这些结果;本例则按金额从小到大填表。两者都利用重复子问题,区别在于求解顺序和组织方式。
贪心算法每一步直接作出一个选择,通常需要证明这个选择可以导向全局最优;动态规划在这里比较所有合法的最后一枚。前面的反例说明,对任意正整数面额,不能假定“总拿最大面额”一定正确。
八、练习:把使用的硬币也找出来
当前方法只返回数量。请扩展它,让 [1, 3, 4]、目标 6 还能返回一种最优方案 [3, 3]。
提示:每次某个 coin 让 dp[value] 变得更小,就另外记录“金额 value 的最后一枚选了 coin”。求解完成后,从目标金额开始,取出记录的面额、从金额中减掉它,重复直到零。
无法凑出时不要进入还原过程;目标为零时,方案应为空列表。有多个最优方案时,返回任意一个即可。验收除了检查数量,还要检查方案之和等于目标,每个面额都来自输入。
如果题目改成“有多少种凑法”,状态含义和转移就需要重新设计,硬币顺序是否视为不同方案也必须先说明。不能只把本例的 min 换成加法,就认为完成了另一道题。
至此,这个系列已经走过线性扫描、查找、排序、遍历、枚举和最优子问题。接下来可以用小规模输入练习独立推导,再逐步学习链表、堆、图的最短路与更多动态规划模型。每次换题,先重新写出输入约束和状态含义,已有代码才容易成为可以调整的工具。
If this article helped you, please share it with others!
Some information may be outdated






