mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
2351 words
6 minutes
算法入门(八):从最少硬币理解动态规划
2026-10-21

有面额为 1、3、4 的硬币,每种都可以使用任意多枚。要恰好凑出金额 6,最少需要几枚?

每次尽量选择大面额,会得到 4 + 1 + 1,共三枚。但 3 + 3 只要两枚。这个例子说明:当前看起来最划算的一步,未必能组成整体最好的方案。

本篇用这个问题学习动态规划:把原问题拆成可以复用的子问题,保存每个子问题的结果,再按依赖顺序求出最终答案。示例使用 Java 17 及以上版本。系列目录也列出了前面关于数组、递归和回溯的文章。

一、先明确这道题允许做什么#

输入包含面额数组 coins 和目标金额 amount。所有面额必须是正整数,每种硬币可以重复使用。目标是恰好凑出金额的最少硬币数量。

coins = [1, 3, 4], amount = 6 → 2
coins = [2], amount = 3 → -1
coins = [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] + 1
dp[a] = 所有合法候选数量中的最小值

这就是状态转移。它把当前状态与更小的状态联系起来。

初值只有一个确定答案:dp[0] = 0。其他金额暂时未知,应标记为不可达,不能把它们也默认当作零。

因为所有面额都大于零,所以 a - coin < a。只要按照金额 1、2、3……amount 的顺序计算,当前状态需要的较小状态就已经准备好。

现在可以在纸上完成 [1, 3, 4]、目标 6 的计算:

金额 a可选的最后一枚及候选数量dp[a]
0不用硬币0
11:dp[0] + 1 = 11
21:dp[1] + 1 = 22
31:3 枚;3:1 枚1
41:2 枚;3:2 枚;4:1 枚1
51:2 枚;3:3 枚;4:2 枚2
61: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.java
java CoinChange

预期输出:

2
-1
0

三行分别覆盖普通可达情况、无法凑出的金额和零金额。继续验证 [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 换成加法,就认为完成了另一道题。

至此,这个系列已经走过线性扫描、查找、排序、遍历、枚举和最优子问题。接下来可以用小规模输入练习独立推导,再逐步学习链表、堆、图的最短路与更多动态规划模型。每次换题,先重新写出输入约束和状态含义,已有代码才容易成为可以调整的工具。

Share

If this article helped you, please share it with others!

算法入门(八):从最少硬币理解动态规划
https://mizuki.mysqil.com/posts/algorithm-08-dynamic-programming/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents