1. 题目拆解与考点定位1.1 先读懂这道题在问什么LeetCode 518题名叫“零钱兑换 II”。很多朋友一看到“零钱兑换”四个字脑子里立刻跳出 322 那道求最少硬币数的题然后就开始套贪心或者套 BFS结果越写越偏。518 这道题问的完全不是“最少用几枚硬币”它问的是给定一个总金额 amount和一堆不同面额的硬币返回凑成这个总金额有多少种不同的组合方式。这里有几个关键词要划重点。第一是“组合”不是“排列”。什么区别组合不考虑硬币出现的先后顺序比如 221 和 122 算同一种方案排列则会把这两种算成两种不同的方案。很多人在第一次做这道题的时候代码写出来结果偏大多半就是栽在这个地方。第二是“每种面额的硬币数量无限”这就直接决定了这道题是“完全背包”模型而不是 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 的这枚硬币即 i1coins[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 种组合是5221211111111写法B算出来 dp[5] 9它把 122、212、221 这些都当成了不同方案。所以如果你去跑这道题出现答案偏大的情况90% 以上是遍历顺序写反了。3.2 用维度坍塌的视角理解顺序问题为什么两种顺序会有这种差异我在二维 DP 的视角下带你看一遍就清楚了。写法A对应二维状态转移时我们的递推是每一行处理一种新硬币从左往右更新 dp[j]。也就是说更新 dp[j] 时dp[j - coin] 已经包含了“当前这种硬币已经用过多次”的可能性但还没有包含“未来硬币”的可能性。每一轮外层循环只引入一种新硬币对内层循环的所有金额而言方案永远只由「已遍历过的硬币种类」组成。这样一种组合的产生过程实际上是“随着硬币种类被逐个允许使用而累积起来的”不会出现因为调整硬币使用顺序而产生多条重复路径的问题所以得到的是组合数。写法B对应的是外层循环对于每个金额 j内层枚举每一种硬币。更新 dp[j] 时dp[j - coin] 可能是由任意一种硬币甚至包括未来的硬币顺序组成的。这就相当于把“最后一枚是哪枚硬币”当成了一种独立的区分标准于是 122、212、221 就被数成了三种方案这就是排列数。一句话总结组合问题先遍历物品再遍历容量排列问题先遍历容量再遍历物品。这个结论可以作为一个模板记下来做题的时候直接套。3.3 如果真写成排列数了怎么快速自查有些时候你代码写完一跑发现答案比预期大但又不知道是哪儿的问题。我教你一个超快的自查手段拿一组非常小的用例跑一下比如 coins [1, 2]amount 3。正确答案是 2 种组合21 和 111注意 12 和 21 是同一个组合只能算一次。 如果你写成排列顺序跑出来是 3111、12、21。这个小用例几乎不用算心算都能验证非常适合定位错误。建议大家在本地测试的时候养成“先用最小用例心算预期结果”的习惯这比直接看代码逻辑找错要快得多。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 有多少种方案”唯一的区别是它把“组合”换成了“排列”允许 121 和 112 算两种。于是代码只需要把循环顺序内外交换一下其余什么都不动# 排列数版本对应 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 这道题上练出来的。如果你看完这篇总结还是觉得哪儿没通我建议你做一件事别急着刷下一题拿张纸分别按两种遍历顺序手推一遍 amount5, coins[1,2,5] 的 dp 数组变化过程。推完那两张表你对“遍历顺序决定组合还是排列”这个点的理解会比看我写十篇总结都管用。