1. 题目拆解与考点定位
1.1 先读懂这道题在问什么
LeetCode 518，题名叫“零钱兑换 II”。很多朋友一看到“零钱兑换”四个字，脑子里立刻跳出 322 那道求最少硬币数的题，然后就开始套贪心或者套 BFS，结果越写越偏。518 这道题问的完全不是“最少用几枚硬币”，它问的是：给定一个总金额 amount，和一堆不同面额的硬币，返回凑成这个总金额有多少种不同的组合方式。
这里有几个关键词要划重点。第一是“组合”，不是“排列”。什么区别？组合不考虑硬币出现的先后顺序，比如 2+2+1 和 1+2+2 算同一种方案；排列则会把这两种算成两种不同的方案。很多人在第一次做这道题的时候，代码写出来结果偏大，多半就是栽在这个地方。第二是“每种面额的硬币数量无限”，这就直接决定了这道题是“完全背包”模型，而不是 0-1 背包。硬币可以重复取，但组合不能重复算。
1.2 为什么说它是动态规划的经典教材
518 这道题在动态规划题目里的地位，相当于“排序算法里的快排”——你几乎不可能绕过它。原因有两点。
第一，它把“完全背包求组合数”这个模型讲得非常纯粹。没有复杂的剪枝，没有多维状态叠加，核心就两件事：状态定义和遍历顺序。而“遍历顺序”恰恰是背包类题目里最让新手头疼的坑。先遍历物品还是先遍历容量，看起来只是换了两行代码的顺序，结果却从“组合数”变成了“排列数”，这种微妙的差异只有在实战中踩过坑才会真正记住。
第二，它是一大批题目的“母题”。后面你遇到求子集和、求方案数的题目，比如 377 组合总和 IV、494 目标和，甚至一些二维背包变种，本质上都是从 518 这个模型延伸出来的。把 518 吃透了，这一整类题目你都有了底子。
2. 状态设计与递推公式的深层逻辑
2.1 dp数组到底该存什么
先给结论：我们定义一个一维数组 dp，其中dp[i] 表示凑成金额 i 的组合方案数。最终答案就是 dp[amount]。
这个定义看起来平平无奇，但你得想清楚一个问题：为什么要用一维数组？很多教程直接告诉你“优化成一维”，却不解释为什么能优化。
二维的思路其实是这样的：dp[i][j] 表示“使用前 i 种硬币（面额从 coins[0] 到 coins[i-1]），凑成金额 j 的方案数”。你会发现，在递推过程中，当前这一行的状态只依赖上一行的状态，或者说在完全背包的场景下，依赖当前行靠前位置的状态。既然每行用完就不再回头用了，我们完全可以用一维数组原地滚动更新。这是“滚动数组”优化，不是凭空拍脑袋的压缩。
从另一个角度理解：dp[i] 本身就是一个“累积方案数”的概念。每加入一种新的硬币面额，我们就把它能贡献的方案数累加到原来的 dp[i] 上。这种“累加”思路贯穿整个背包问题体系，也是理解后续代码的关键。
2.2 递推公式是怎么来的
递推公式就一行：
dp[j] += dp[j - coins[i]]很多人在第一次看到这个式子的时候觉得莫名其妙，这到底是怎么从“方案数”推导出来的？
我用一个实际场景拆给你看。假设硬币面额是 [1, 2, 5]，总金额是 5，现在我们关注的是面额为 2 的这枚硬币（即 i=1，coins[1]=2）。当我们计算 dp[5] 时，这个式子表达的意思是：如果我们在凑成金额 3 的方案基础上，再放一枚面额为 2 的硬币，就能凑成 5。所以 dp[5] 应该把 dp[3] 的所有方案都加进来，因为每种方案都能通过加一枚 2 元硬币转化成一个新的“包含硬币2”的方案。
本质上，这是在枚举“当前这枚面值为 coins[i] 的硬币是否作为组合中的最后一枚加入”。但注意，完全背包允许重复取，所以我们要从小到大正序遍历 j，这样在累加 dp[j - coins[i]] 的时候，那个 dp[j - coins[i]] 本身可能已经包含使用了多枚 coins[i] 的方案，从而实现了“无限取用”的效果。这个理解极其重要，因为如果你把 j 的遍历方向反过来，变成从大到小，那就退化成了 0-1 背包（每种硬币只能取一次）。
2.3 边界条件 dp[0] = 1 怎么理解
dp[0] = 1，意思是“凑成金额 0 的方案数为 1”。什么？金额为 0 还能有一种方案？是的，就是“一个硬币都不选”这种空方案。
这个初始化是递推的基石。如果 dp[0] = 0，那么推下去整个数组全是 0，什么都不成立。你可以把 dp[0] 看作一个“辅助锚点”：当 j 正好等于 coins[i] 时，dp[j - coins[i]] = dp[0] = 1，这表示“只用一枚 coins[i] 就能凑成 j”的这个方案被正确计入。没有这个锚点，所有“单枚硬币方案”都会漏掉。
老手其实看待 dp[0]=1 还有一种感觉：它在数学上对应了“空集是任何集合的子集”这件事，也是组合计数里的单位元。新手不用太纠结这层，但记住这个初始化不可改动就对了。
3. 核心难点：遍历顺序为什么决定了组合还是排列
3.1 同一段代码，换个顺序结果天差地别
这是 518 最值得深挖的考点。先看两份代码片段，差别只有一个：两层 for 循环的顺序。
# 写法A：外层遍历硬币，内层遍历金额 —— 得到组合数 for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin]# 写法B：外层遍历金额，内层遍历硬币 —— 得到排列数 for j in range(amount + 1): for coin in coins: if j >= coin: dp[j] += dp[j - coin]实测一下：coins = [1, 2, 5]，amount = 5。
写法A算出来 dp[5] = 4，这是正确答案，对应的 4 种组合是：
- 5
- 2+2+1
- 2+1+1+1
- 1+1+1+1+1
写法B算出来 dp[5] = 9，它把 1+2+2、2+1+2、2+2+1 这些都当成了不同方案。所以如果你去跑这道题，出现答案偏大的情况，90% 以上是遍历顺序写反了。
3.2 用维度坍塌的视角理解顺序问题
为什么两种顺序会有这种差异？我在二维 DP 的视角下带你看一遍就清楚了。
写法A对应二维状态转移时，我们的递推是：每一行（处理一种新硬币）从左往右更新 dp[j]。也就是说，更新 dp[j] 时，dp[j - coin] 已经包含了“当前这种硬币已经用过多次”的可能性，但还没有包含“未来硬币”的可能性。每一轮外层循环只引入一种新硬币，对内层循环的所有金额而言，方案永远只由「已遍历过的硬币种类」组成。这样，一种组合的产生过程，实际上是“随着硬币种类被逐个允许使用而累积起来的”，不会出现因为调整硬币使用顺序而产生多条重复路径的问题，所以得到的是组合数。
写法B对应的是：外层循环对于每个金额 j，内层枚举每一种硬币。更新 dp[j] 时，dp[j - coin] 可能是由任意一种硬币（甚至包括未来的硬币顺序）组成的。这就相当于把“最后一枚是哪枚硬币”当成了一种独立的区分标准，于是 1+2+2、2+1+2、2+2+1 就被数成了三种方案，这就是排列数。
一句话总结：组合问题先遍历物品再遍历容量，排列问题先遍历容量再遍历物品。这个结论可以作为一个模板记下来，做题的时候直接套。
3.3 如果真写成排列数了，怎么快速自查
有些时候你代码写完一跑，发现答案比预期大，但又不知道是哪儿的问题。我教你一个超快的自查手段：拿一组非常小的用例跑一下，比如 coins = [1, 2]，amount = 3。
正确答案是 2 种组合：2+1 和 1+1+1（注意 1+2 和 2+1 是同一个组合，只能算一次）。 如果你写成排列顺序，跑出来是 3：1+1+1、1+2、2+1。
这个小用例几乎不用算，心算都能验证，非常适合定位错误。建议大家在本地测试的时候，养成“先用最小用例心算预期结果”的习惯，这比直接看代码逻辑找错要快得多。
4. 代码实现与边界处理
4.1 一份可以直接“抄作业”的参考代码
这里给出 Python 和 Java 两个版本的实现，都是最精简的写法，推荐大家直接背这个骨架。
# Python：零钱兑换II —— 完全背包求组合数 def change(amount: int, coins: list[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 # 凑成0的方案数为1（空组合） for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin] return dp[amount]// Java：零钱兑换II class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int j = coin; j <= amount; j++) { dp[j] += dp[j - coin]; } } return dp[amount]; } }4.2 几个容易被忽略的细节
第一个细节，内层循环的起始位置是j = coin，不是j = 1。这是因为当 j < coin 时，dp[j - coin]访问的是负数下标，会导致数组越界。在 Java 里会直接抛异常，在 Python 里则会把数组末尾的元素取出来，产生诡异的错误结果。如果你用的是 Python 又省略了这个下标检查，很容易出现“答案怎么莫名其妙变大”的情况。
第二个细节，coins 数组要不要排序？答案是：不用排。这个题目中硬币的遍历顺序并不影响最终组合数的结果。你可以试试把 coins 换成 [5, 2, 1]，跑出来的答案仍然是 4。因为组合数只关心“哪些面额参与了”，不关心“参与的先后顺序”。有的同学可能被其他题目的惯性影响，总想先排序，在这道题里完全多此一举，而且排了也不会错，只是浪费了 O(nlogn) 的时间。
第三个细节，dp[j] 累加会不会溢出？根据题目约束，最终结果保证在 32 位有符号整数范围内（至少中文版原题约束如此），Java 用 int 就够了；Python 则完全没有溢出的烦恼，因为它的整数是任意精度的。但如果题目要求你处理的是“超大金额”的变体，比如方案数上万亿，那你就要考虑取模或者用 long，这一点在面试中值得主动和面试官确认。
4.3 空间复杂度还能不能优化？——已经到底了
时间复杂度 O(amount * n)，其中 n 是硬币种类的数量，空间复杂度 O(amount)。这已经是这个模型下最简的一维版本了。
有人可能会问：能不能把空间也压缩到 O(1)？答案是不能，因为 dp 数组每个金额位置的状态都需要被保存。不过硬币种类很多、amount 比较小时，可以考虑先用一个哈希表收集可用面额，减少无效遍历，但收益通常有限，属于过度优化，不建议在实战中这么做。
5. 常见问题与排查技巧实录
5.1 为什么我的 dp[0] 初始化为 0，结果永远是 0？
这大概是我在评论区看到最多的问题。你这么一初始化，整个递推的“种子”就没有了。dp[j] += dp[j - coin] 这个式子，本质是在把之前累积的方案数往当前位置搬运。dp[0]=0 就表示“空组合都不存在”，那任何单枚硬币凑金额的方案自然不可能被计入。于是 dp 数组永远是一堆 0。
我的建议是把 dp[0]=1 当成这个系列的默认配置，不要问为什么，先记下来，等你能独立推导出 2.2 节那个递推过程的时候，自然就理解它的意义了。
5.2 我把遍历顺序写成了“外层金额、内层硬币”，结果比预期大了好几倍，这正常吗？
太正常了，因为你写成了排列数模型。这个题目我前面已经详细拆过，出现这种情况直接调整循环嵌套就可以了。如果你是在面试现场发现自己犯了这个错，可以坦率地告诉面试官：“我意识到了，这是一个组合问题，应该先遍历硬币种类再遍历金额”，然后快速改掉，这反而能体现你对这个模型理解得透。
5.3 二维 DP 我能写对，为什么一维写法老出错？
二维版本是这样的：
dp2 = [[0] * (amount + 1) for _ in range(len(coins) + 1)] dp2[0][0] = 1 for i in range(1, len(coins) + 1): dp2[i][0] = 1 # 任何硬币集合凑0，都有1种空方案 for j in range(1, amount + 1): if j < coins[i-1]: dp2[i][j] = dp2[i-1][j] else: dp2[i][j] = dp2[i-1][j] + dp2[i][j - coins[i-1]]注意这个二维版本里，当 j >= coins[i-1] 时，第二项用的是dp2[i][j - coins[i-1]]，也就是“当前这一行靠前位置”的值，而不是上一行的值。这就是完全背包和 0-1 背包在二维公式上的根本区别：0-1 背包第二项是 dp2[i-1][j - coins[i-1]]，完全背包是 dp2[i][j - coins[i-1]]。
从二维转一维时，如果你保留了这个“当前行更新”的语义，内层 j 就必须从小到大遍历，否则你取到的就是“上一行旧值”而不是“当前行新值”，完全背包性质就丢了。每次写一维代码前，我都建议你在心里过一遍这个二维推导，能从根本上避免顺序写反。
5.4 遇到“金额为零”的特殊用例怎么办？
如果 amount = 0，直接返回 dp[0] = 1。这是很多边界用例测试会考的。不管 coins 是什么，凑 0 的方案就是“什么都不选”这一种。有的同学条件反射地觉得“没有钱当然没有方案”，直接返回 0，反而掉进坑里。你去提交看看，这类边界用例在 LeetCode 上经常出现。
5.5 这个代码横扫 debug 还显示超时，可能是什么问题？
如果硬币面额列表很长、amount 又很大，O(amount * n) 的复杂度可能会达到千万级别，通常在正常时间内可以跑完。如果真的超时了，大概率不是算法本身的问题，而是你无意中写了死循环，比如 while 循环忘了递增，或者递归版本栈溢出。518 这道题标准解法是迭代 DP，我一般不推荐用递归爆搜去解，因为状态太多而且必然重复计算。
6. 变形与延伸：这套思路还能用到哪些题
6.1 和 377 组合总和 IV 的对比
377 这道题问的也是“凑成 target 有多少种方案”，唯一的区别是它把“组合”换成了“排列”，允许 1+2+1 和 1+1+2 算两种。于是代码只需要把循环顺序内外交换一下，其余什么都不动：
# 排列数版本，对应 377 题 for j in range(target + 1): for coin in coins: if j >= coin: dp[j] += dp[j - coin]所以你在面同一类题目时，可以先问自己一句：“顺序不同的方案算两种吗？”这个问题的答案直接决定了遍历顺序。我们甚至可以说：518 和 377 就是一对镜像题，吃透一个等于吃透两个。
6.2 完全背包求组合数的其他变体
还有一个很经典的变体，就是把硬币面额换成物品重量，变成一个“固定容量的背包能装出多少种组合”的问题。例如，某种“组和总和 IV”或者“划分相等子集”的题目，只是 dp 的含义从“方案数”变成“是否存在”或者“最大价值”。核心的状态转移思想完全一致：你枚举一个个物品，然后正序遍历容量，保持完全背包的“可取无限次”特性。
遇到这类题，我的做题套路是先写一个朴素二维 DP，验证思路成立后再压缩成一维。这样做虽然多花了一点时间，但能最大程度避免遍历顺序的失误。
6.3 面试官会怎么追问
我在模拟面试中经常碰到面试官对 518 做三个方向的追问：
- 如果每种硬币有数量上限，怎么改？——这就成了多重背包，需要在内层再加一层 k 循环，或者用二进制拆分优化。
- 如果要求“输出所有组合”而不是“组合数”，怎么处理？——那就不能只用 DP 计数了，需要回溯法去收集所有路径，因为 DP 只记录数量，不记录方案本身。
- 如果硬币面额列表里有重复面额怎么办？——这不会影响结果，重复的面额只是让同一个面额被遍历多次，但组合数不会变多，因为重复面额不会产生新的组合。不过在一个严格的设计里，可以先对 coins 去重，减少无用遍历。
把 518 连同这三个追问都准备到位，我对你的信心会高很多，因为这说明你不只会背模板，而是真的理解了背包问题的几个关键变量。
最后想说的一点心得
说实话，518 是我个人最爱拿来讲“动态规划入门”的题目之一，因为它足够简单，简单到核心逻辑就十行代码；但它又足够深刻，深刻到遍历顺序这一个细节就能绊倒一大片人。我自己第一次刷这道题的时候，也是先写出了排列数的版本，跑出 9 那个答案，愣了好一会儿才反应过来问题出在哪。从那以后，我碰到任何“求方案数”的题，第一反应永远是先确认“组合还是排列”，再动手写循环。这种肌肉记忆，就是从 518 这道题上练出来的。
如果你看完这篇总结还是觉得哪儿没通，我建议你做一件事：别急着刷下一题，拿张纸，分别按两种遍历顺序手推一遍 amount=5, coins=[1,2,5] 的 dp 数组变化过程。推完那两张表，你对“遍历顺序决定组合还是排列”这个点的理解，会比看我写十篇总结都管用。
