题目
LC 322 零钱兑换：给你一个整数数组
coins 表示不同面额的硬币，以及一个整数
amount 表示总金额。计算并返回可以凑成总金额所需的
最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回
-1。每种硬币的数量是
无限的。
输入: coins = [1, 2, 5], amount = 11
输出: 3 （11 = 5 + 5 + 1）
输入: coins = [2], amount = 3
输出: -1 （2 怎么翻倍都凑不出奇数）
它是最标准的
完全背包 · 求最小值：物品可以无限取，要的是"最少件数"。这类题唯一的门槛不在递推式（一行就写完），而在两个地方 ——
∞ 的初始化，以及
内层金额的遍历方向。后者是本文的主角：同一段代码，金额正序得到
3，金额逆序得到
-1。
一、核心洞察：dp 定义与状态转移
暴力的思路是枚举"各用几枚"，组合数会爆炸。换成
逐个金额地逼近：
不问"用哪些硬币"，而问"凑出金额 x 最少要几枚"。
于是定义：
dp[x] = 凑出金额 x 所需的最少硬币枚数；dp[0] = 0（零元一枚都不用）；- 其余全部初始化成 ∞（先假定凑不出，凑得出再往下降）。
递推式只有一行：
dp[x] = min over 每种硬币 c ( dp[x - c] + 1 ) （x - c >= 0）
语义是：
把硬币 c 当作"最后一枚"去试 —— 剩下
x - c 的最优解已经知道，补上这一枚就是一条候选路径。
x 从
1 到
amount 正序推进，等算
dp[x] 时，用到的
dp[x-c]（下标更小）早就写好了。
def coinChange(coins, amount):
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for c in coins:
if x >= c:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
两个细节决定了成败：
∞ 而不是 0：用 0 初始化等于宣布"任何金额都凑得出、而且一枚就够"，min 会把答案大面积压成 1。∞ 才是"先假定凑不出"，配合 min 让它有机会被真正的路径顶下去。- 内层金额正序：见下一节，这是"硬币可以无限复用"的开关。
二、为什么"正序"是完全背包的指纹
把上面的写法换成背包的视角 ——
外层面额、内层金额：
for c in coins: # 一种一种硬币地放
for a in ??: # 金额怎么遍历？
if a >= c:
dp[a] = min(dp[a], dp[a - c] + 1)
变量只剩一个：内层
a 的方向。
正序（a: 1 → amount）—— 完全背包（LC 322 要的）
处理到金额
a 时，
dp[a-c]（下标更小）
这一轮已经更新过，而且它自己可能就是用硬币
c 凑出来的。于是
dp[a] = dp[a-c] + 1 天然允许"
再叠一枚 c"。硬币无限复用就发生在这里：
[1,2,5] 凑
11，
dp[11] 从
dp[10] 借力，
dp[10] 从
dp[5] 借力，
5+5+1 三枚，答案
3。
逆序（a: amount → 1）—— 0-1 背包（换题了）
处理到金额
a 时，
dp[a-c] 这一步
还没被本轮碰过（下标更小、要等后面才轮到），读到的是
上一轮留下的旧值。等价于"每枚硬币最多用一次" ——
[1,2,5] 三枚总面额只有
8，凑
11 永远无解，答案
-1。
一句话记住分界：
正序读"同一轮已经写好的自己"，逆序读"上一轮留下的自己"。
所以：
322 必须正序；而
416 分割等和子集、
1049 最后一块石头重量 II 这类"每件只能用一次"的，才反过来必须
逆序。这不是风格差异，是题意差异。
三、动画怎么看
动画一（
algo-viz--lc322）：顶部是
dp[0..11] 整行金额格，当前金额金框、来源格绿框，两者之间一条弧线把"从哪来"画清楚；中部是候选硬币行 —— 每枚硬币一格，写出
dp[x-c] + 1 的现场打分，获胜者描金、超出金额的格子虚线划掉；横幅给出这一格的
min(...) 完整算式。填完 11 格之后，动画会继续走
回溯帧：顺着
chosen 前驱表从
11 → 10 → 5 → 0 走回起点，把最优组合
5 + 5 + 1 从表里"捞"出来 —— 只记枚数是还原不出组合的。
动画二（
algo-viz--lc322order）：上下两块面板，方程
逐字相同，只有内层金额的方向不同。上面正序（本轮从左往右扫，已扫区间
1 → a），下面逆序（从右往左扫，已扫区间
a → 11）。每帧按"本轮第几步"对齐 —— 第
j 帧里上面处理金额
j、下面处理金额
12 - j。盯住
来源格：正序面板读到的永远是"本轮的新值"，逆序面板读到的永远是"上一轮的老值"。跑完三枚硬币，上面
dp[11] = 3，下面
dp[11] = ∞。
四、完整推演表
动画一：
coins = [1, 2, 5]，
amount = 11（与动画默认一致）。
最终
dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]，返回
3。注意第 11 格：三枚硬币给出的候选是
3, 4, 3，
1 和
5 打平 —— 取第一个（同分不换），于是回溯链走
11 → 10 → 5 → 0，组合是
5 + 5 + 1。
动画二：同一组数据，看两块面板跑完每枚硬币之后的样子。
正序那列的每一格都是"这一轮刷过的新值"顶上去的；逆序那列从右往左刷，但每枚硬币只肯出手一次，
dp[11] 到最后还是
∞ → 返回
-1。
五、同族题：518 / 279 / 377 / 139 / 416
322 是"完全背包求最小值"。同一副骨架换个问法，就是一条完整的题链：
- LC 279 完全平方数：硬币就是
1, 4, 9, 16, ...，问凑出 n 的最少个数 —— 与 322 逐字同构，连代码都只改一行（把 coins 换成平方数序列）。
- LC 518 零钱兑换 II：完全背包但求方案数。转移变成
dp[a] += dp[a-c]，而且必须外层硬币、内层金额正序 —— 这个顺序把"同一种组合的不同排列"去掉了，数的才是组合数。
- LC 377 组合总和 IV：同一行加法、但外层金额、内层硬币 —— 顺序反过来，数的就变成了排列数。377 和 518 的差别只有循环嵌套的顺序，值得对着看一眼。
- LC 139 单词拆分：完全背包的布尔版，
dp[a] |= dp[a-len] && s 的这一段在字典里。
- LC 416 分割等和子集：求"能否恰好装满
sum/2"，但每件元素只能用一次 —— 这是 0-1 背包，内层金额必须逆序（正是本文动画二右边那块）。LC 494 目标和、LC 1049 最后一块石头重量 II 同理。
把它们排成一列看：
背包的容量维就是金额维，物品就是硬币；"无限件"用正序，"每件一次"用逆序；求最值用 min/max，求方案数用 +。 322 只是这条坐标轴上的一个点。
六、Java 版
class Solution {
// LC 322：完全背包求最小 —— 与推演表逐帧一致
public int coinChange(int[] coins, int amount) {
int INF = amount + 1; // 哨兵：比"全用 1 元"还大一，且 +1 不会溢出
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int x = 1; x <= amount; x++) {
for (int c : coins) {
if (x >= c && dp[x - c] + 1 < dp[x]) {
dp[x] = dp[x - c] + 1; // 用更新前的 dp[x-c]；正序保证它可能已含 c
}
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
}
class Solution {
// LC 322：配一张前驱表就能还原"用了哪些硬币"
public int coinChange(int[] coins, int amount) {
int INF = amount + 1;
int[] dp = new int[amount + 1];
int[] chosen = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int x = 1; x <= amount; x++) {
for (int c : coins) {
if (x >= c && dp[x - c] + 1 < dp[x]) {
dp[x] = dp[x - c] + 1;
chosen[x] = c;
}
}
}
if (dp[amount] == INF) return -1;
List<Integer> picked = new ArrayList<>();
for (int cur = amount; cur > 0; cur -= chosen[cur]) picked.add(chosen[cur]);
// picked 即最优组合（回溯顺序）
return dp[amount];
}
}
class Solution {
// LC 322 的另一种视角：BFS 最短路（顺带能出组合）
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dist = new int[amount + 1];
Arrays.fill(dist, -1);
Deque<Integer> queue = new ArrayDeque<>();
dist[0] = 0;
queue.addLast(0);
while (!queue.isEmpty()) {
int cur = queue.pollFirst();
for (int c : coins) {
int next = cur + c;
if (next <= amount && dist[next] == -1) {
dist[next] = dist[cur] + 1;
if (next == amount) return dist[next];
queue.addLast(next);
}
}
}
return -1;
}
}
注意 Java 里的哨兵：用
amount + 1（而不是
Integer.MAX_VALUE）当"无穷大"，因为
Integer.MAX_VALUE + 1 会溢出成负数，
min 立刻选错。
七、边界情况
amount = 0：直接返回 0，不必进循环 —— "一枚都不用"就是答案；- 凑不出：
dp[amount] 停在 ∞，返回 -1。[2] 凑 3、[3,7] 凑 5 都是这类；
- 硬币比金额大：
x - c < 0，这枚硬币永远装不下，直接跳过（也可以先把 coins 里大于 amount 的过滤掉）；
- 单枚命中：
[7] 凑 7 → 1，[7] 凑 14 → 2（复用同一枚，靠的正是正序）；
- 硬币齐全：只要有
1，任何金额都可达，dp 全程有限 —— 这也是很多测试用例的"安全带"；
- 面额重复：
[1,1,2] 与 [1,2] 答案相同（同分不换，只是可能选到不同那枚），不影响正确性；
- 溢出：Java 用
amount + 1 当哨兵；Python 用 float('inf')；JS 用 Infinity —— 别用 int 上界硬加一。
八、复杂度
k 是硬币
种数。二维完全背包的一维化，靠的正是"内层金额正序"：
dp[x] 只依赖同一行的更小下标，压掉"用到第几种硬币"这一维后语义不变 —— 反过来说，
逆序就是压错了方向的后果。
九、常见坑
∞ 初始化成 0：min 立刻把一切都压成 0 或 1。记住语义是"先假定凑不出"。- 内层金额逆序：程序照跑、样例照过（如果硬币够多），但题意已经悄悄变成 0-1 背包 ——
[1,2,5] 凑 11 会返回 -1。
- 贪心先拿大面额：
[1,3,4] 凑 6，贪心拿 4 之后剩 2，得 4+1+1 = 3 枚；正确答案是 3+3 = 2 枚。面额不整除时必须 DP。
- 忘了
amount = 0 短路：逻辑上 dp[0] = 0 已经覆盖，但如果代码里有除零、取模或"至少一枚"的假设，就会翻车。
- 返回
dp[amount] 而不是 -1：题面要求凑不出时返回 -1，直接返回 ∞/大数会判错。
- 只记枚数、还原不了组合：需要组合时得再配一张前驱表（
chosen[x]），从 amount 顺链走回 0。
- Java 用
Integer.MAX_VALUE 当 ∞：MAX_VALUE + 1 溢出成负数，min 会选中它。用 amount + 1。
- 把 322 与 518 的顺序规则混用：322 求 min，外面对金额 / 内层硬币也成立；518 求方案数，必须外层硬币、内层金额正序，否则数的是排列（那是 377）。
- 忘记过滤大于
amount 的硬币：不影响正确性，但会让每轮多跑无用的分支；贪心类解法里则会导致错误。
十、面试怎么答
第一段 · 定义与转移：
dp[x] = 凑出金额
x 的最少硬币枚数，
dp[0] = 0、其余
∞，
dp[x] = min(dp[x-c] + 1)，金额正序推进。说清
∞ 为什么不能用
0。
第二段 · 为什么正序：外层硬币、内层金额，正序时
dp[x-c] 是本轮已更新的值，允许"再叠一枚同一硬币" —— 这就是完全背包；逆序读到的是上一轮的旧值，退化成 0-1 背包。
这一段是这题的区分度所在，主动说出来比写对代码更值钱。
第三段 · 换个视角：把金额当作图上的点、每枚硬币当作一条单位权边，答案就是
0 → amount 的
最短路，BFS 一遍即可，
O(amount × k)。DP 与 BFS 在这里等价 —— 这个视角在追问"打印最优组合"时特别顺手（BFS 记录前驱即可）。
追问连跳：
- 要
方案数 → LC 518（
dp[a] += dp[a-c]，外层硬币、内层正序）；要
排列数 → LC 377（循环顺序对调）；
- 物品
每件只用一次 → LC 416 / 494 / 1049，内层金额
逆序；
- 硬币面额变成平方数 → LC 279，代码只换序列；
- 要
还原组合 → 加
chosen[x] 前驱表，从
amount 回溯到
0。
一句话收尾："零钱兑换只有一台机器 ——
dp[金额] 的完全背包，区别只在方向、在
min 还是
+。"
结语
322 的全部难度浓缩在一行初始化（
∞）和一层循环方向（正序）里。
∞ 决定了"凑不出"这件事能不能被表达，正序决定了"硬币能不能重复用" —— 前者是定义问题，后者是题意问题。把这两处讲清楚，518、279、377、416 就都只是同一台机器换了个参数。
下一篇见。