零钱兑换这道题我在实际面试和帮人模拟面试里见过太多次了。不少人能背出dp[i] min(dp[i], dp[i - coin] 1)这行方程但面试官一旦追问“为什么贪心不行”“为什么先遍历硬币再遍历金额”就当场卡壳。这篇不打算只贴个标准答案而是从面试考察的角度把这道题从暴力递归到动态规划再到路径回溯和变体题完整拆一遍。无论你是刚开始刷题还是准备冲刺大厂应该都能从中找到自己能用的东西。1. 面试官问零钱兑换到底在观察什么1.1 从题目本身说起LeetCode 322题题面其实很短给定不同面额的硬币coins和一个总金额amount计算可以凑成总金额所需的最少硬币个数。如果没有任何一种组合能凑成就返回 -1。每种硬币数量无限并且每枚硬币的面额是一个整数。注意这里有个最容易踩的认知混淆LeetCode 518题“零钱兑换II”问的是“有多少种组合方式”而322题问的是“最少需要几枚硬币”。一个是方案数的统计一个是数量的最优化虽然都是动态规划状态转移方程完全不同。面试时如果连题都没听清就开始写基本GG。1.2 高频题背后的原因这道题能成为面试高频题不是因为它难——恰恰相反它的难点阈值被控制得很好。它考察的是动态规划最基本的三个能力能不能正确定义状态dp[i]表示什么能不能推导出递归关系状态之间如何转移能不能识别重叠子问题并说出暴力解为什么慢这三个能力刚好覆盖了动态规划的入门核心。面试官通过这一道题就能快速判断你是真的理解了DP还是只会背套路模板。我面过一些候选人状态转移方程写得飞快但问他“为什么不能用贪心”时一脸茫然。这种表现其实比“不会做但能讲清思路”更减分因为背后的信号是刷题靠记忆没有形成自己的思考链路。1.3 这道题会怎么变形面试官不会永远只问原题常见的变形方式有把“最少硬币数”改成“输出具体用了哪些硬币”把“每种硬币无限”改成“每种硬币只有一个”01背包把“凑成总额”改成“凑出大于等于某个数的最小值”把“最少两枚”改成“计算组合方案数”金额范围变大问如何优化时间或空间这些都是从322延伸出去的节点。理解了零钱兑换的底层推导逻辑等于同时预习了几个变体题。2. 先别急着写转移方程三个必须跨过的认知坎2.1 为什么贪心在这里不靠谱看到“最少硬币”四个字第一反应很容易是先用大面额再用小面额补齐。这确实是现实中找零的习惯操作但它在算法上并不总是成立。举个例子硬币面额是[1, 7, 10]目标是凑出 14。贪心策略会先选 10剩余 4只能用 4 个 1 补齐一共 5 枚硬币。但最优解是 7 7只需要 2 枚硬币。贪心在这里就失灵了。再比如[1, 3, 4]金额 6贪心会选 4 1 1共 3 枚但 3 3 是 2 枚。那为什么有些情况贪心又是对的比如人民币面额[1, 5, 10, 20, 50, 100]贪心找零通常没问题。因为这种面额组合满足“更优子结构”的特殊条件贪心策略恰好成立。但题目没有保证 coins 具备这种性质所以必须把贪心排除在外。面试时主动说出这个反例能直接证明你不是靠背题。2.2 把问题画成递归决策树动态规划问题普遍可以先用暴力递归去理解。假设金额为F(n)要凑出 n每选一个硬币coin问题就变成“凑出 n - coin”的子问题。于是F(n) min(F(n - coin[0]), F(n - coin[1]), ...) 1边界条件是F(0) 0不需要任何硬币F(负数) 无解这种写法是纯粹的穷举代码不复杂但问题是慢。每层大约有coins.length个分支深度最大接近amount / minCoin最坏情况下是指数级复杂度。在面试现场可以先说出这个暴力版本然后指出它的瓶颈大量重复计算。2.3 重叠子问题到底在哪里很多人背会说“DP能避免重复计算”但说不清重复在哪。以coins [1, 7, 10]、amount 14为例F(14) 会分支出 F(13)、F(7)、F(4) F(13) 又会分支出 F(12)、F(6)、F(3) F(7) 同样会分支出 F(6)、F(0)、F(-3)注意F(6)既在F(13)的分支里又在F(7)的分支里F(3)、F(4)这些节点也会在不同路径上反复出现。每一次重复都意味着同一段计算被重做一遍。递归树越大重复的节点越多这就是指数爆炸的根源。感知到这一步动态规划的核心思路就浮出来了既然反正都要算同一个子问题不如把结果存下来下次直接查表。这也是“重叠子问题 最优子结构”两个DP要素的具体体现。3. 备忘录递归自顶向下也是一个完整可用的版本3.1 memo数组的设计细节自顶向下改法很简单加一个memo数组缓存已经计算过的结果。但这里有一个小坑用什么值表示“没有计算过”。很多初学者用-1既表示“没有计算”又表示“无解”结果覆盖混乱。更稳妥的做法是用一个不可能出现的值表示“未访问”比如-2而-1专门表示“无解”。这样缓存和无效结果就不会混淆。更稳健的完整代码如下function coinChange(coins, amount) { // 初始化 memo-2 表示还没计算过-1 表示无解 const memo new Array(amount 1).fill(-2); function dfs(rem) { if (rem 0) return -1; if (rem 0) return 0; if (memo[rem] ! -2) return memo[rem]; let min Infinity; for (const coin of coins) { const res dfs(rem - coin); if (res ! -1) { min Math.min(min, res 1); } } memo[rem] min Infinity ? -1 : min; return memo[rem]; } return dfs(amount); }这段代码可以直接跑过LeetCode的322题。它的优点是完全符合人脑的递归直觉先拆解问题再缓存结果。3.2 自顶向下为什么能在面试中加分在面试场景里我建议先讲这个版本再讲自底向上。原因很简单它更容易让面试官跟着你的思路走。自顶向下的推导路径是“大问题拆成小问题”这符合人类理解问题的顺序。而自底向上的推导路径是“先算小问题再合出大问题”更适合写代码和性能分析但理解门槛稍高。能同时说出两个方向本身就说明你对DP不是一知半解。不过要注意递归版本在极端情况下可能触发递归栈过深比如amount非常大、硬币面额很小时调用深度会很高。部分面试官会比较在意这点那就顺势引出自底向上的迭代版本。4. 自底向上的动态规划面试中最稳的主流解法4.1 状态定义和转移方程到底怎么来的自底向上的思路是先解决小金额再逐步扩展到大金额。定义dp[i]为“凑出金额 i 所需的最少硬币数”。目标就是求dp[amount]。初始化时dp[0] 0其余位置设为一个很大的数比如Infinity或amount 1因为最坏情况下不可能超过amount枚硬币如果存在1分币的话。转移方程对于每个硬币面额 coin dp[i] Math.min(dp[i], dp[i - coin] 1)这里的加1代表“选择了一枚硬币”。dp[i - coin]是“凑出剩余金额所需的最少硬币数”所以目标金额 i 的最小值就是在所有候选硬币中取最小值。注意i - coin必须大于等于 0。4.2 用手推一遍比背十遍公式管用来看经典例子coins [1, 2, 5]amount 11。初始dp[0] 0 dp[1] ~ dp[11] Infinity用硬币1更新dp[1] 1, dp[2] 2, dp[3] 3, ...全部用1元硬币凑所以 dp 数组依次是金额本身。用硬币2更新时dp[2]从 2 变成 1一枚2元硬币dp[3]从 3 变成 21 2dp[4]从 4 变成 22 2一步步优化上去。用硬币5更新后dp[5]从 5 变成 1直接用1枚5元硬币dp[6]从 6 变成 21 5dp[10]从2变成255也是2dp[11]最终是 3551。手推一次你会明显感觉到这个表的每一格都是在“上一次最优解”的基础上拿一枚新硬币去碰。碰得更优就更新碰不动就保持原状。4.3 遍历顺序为什么是“先硬币后金额”标准写法中外层循环遍历coins内层循环从coin到amount正序推进。这个顺序对322题不是唯一正确解但却是最值得讲给面试官的写法因为接下来和518题做对比时这个习惯能救命。function coinChange(coins, amount) { const dp new Array(amount 1).fill(Infinity); dp[0] 0; for (const coin of coins) { for (let i coin; i amount; i) { if (dp[i - coin] ! Infinity) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } } return dp[amount] Infinity ? -1 : dp[amount]; }不要小看这个“双层循环 一维数组”的结构。它本质上是一个滚动数组一层硬币一轮更新数组里的每个值都会被多次覆盖。由于322求的是最小值即使同一金额通过不同硬币组合反复到达也不会影响“最小值”的准确性。内层正序推进让同一种硬币可以被多次选择正好满足“每种硬币无限使用”的设定。4.4 边界情况的处理套路算法写完后一定要过三个边界测试amount 0返回 0coins [2]amount 3返回 -1coins [1]amount 0返回 0如果你用amount 1作为初始值在判断时要注意dp[i - coin] 1可能超过amount 1吗实际上 dp 值最大不会超过amount在有1分币时)所以amount 1足够作为“无穷大”的替身。用Infinity则更安全它在算术运算里不会溢出只是不能参与某些位运算。面试时提一嘴这个初始化细节观感会很不一样。5. 从最少数量到具体方案路径回溯和它引出的兄弟题5.1 面试官突然追问具体是哪几枚硬币很多题解到dp[amount]就结束了。但面试官有时会加一句“优化一下把具体组合也输出出来。”这就要在更新 dp 时额外记录“当前金额从哪个金额转移而来”。用一个parent数组保存前驱parent[i] i - coin表示凑出 i 的最后一步是从i - coin加上一枚coin得到的。代码扩展如下function coinChangeWithPath(coins, amount) { const dp new Array(amount 1).fill(Infinity); const parent new Array(amount 1).fill(-1); dp[0] 0; for (const coin of coins) { for (let i coin; i amount; i) { if (dp[i - coin] 1 dp[i]) { dp[i] dp[i - coin] 1; parent[i] i - coin; } } } if (dp[amount] Infinity) return []; const path []; for (let cur amount; cur 0; ) { const prev parent[cur]; path.push(cur - prev); // 这一步就是被选中的硬币面额 cur prev; } return path; }比如coins [1, 2, 5]、amount 11可能得到[5, 5, 1]。这个版本面试时相当加分因为大多数人的准备止步于“知道数量”而你还能把方案还原出来。5.2 一阵见血的变形题组合数怎么算如果面试官此时端出518题“有多少种组合”你会发现刚才的遍历顺序突然就变敏感了。组合数的状态转移是dp[i] dp[i - coin]dp[i]表示凑出金额 i 的组合数dp[0] 1。代码function change(amount, coins) { const dp new Array(amount 1).fill(0); dp[0] 1; for (const coin of coins) { for (let i coin; i amount; i) { dp[i] dp[i - coin]; } } return dp[amount]; }关键在于外层必须遍历硬币内层正序遍历金额。这样同一个面额组合只会在固定的硬币顺序里被计算一次不会把[2,1]和[1,2]当成两种方案。如果反过来外层遍历金额、内层遍历硬币结果就会变成排列数。拿amount 3、coins [1, 2]举例正确定义下的组合数是2[1,1,1]和[1,2]但排列数是3多算一个[2,1]。这个例子在面试里一说出来面试官立刻就知道你是真懂而不是背模板。5.3 一个实用的降级判断最大公约数剪枝硬币面额都已知时有一个小优化可以在讨论环节提一下如果所有硬币面额的最大公约数不能整除amount那所有面额组合出来的金额一定也整除不了amount可以直接返回 -1不需要跑DP。比如coins [4, 6]、amount 5因为 gcd(4, 6) 22不能整除5直接返回 -1。这种剪枝在实际比赛中作用不大因为DP本身也能算出同样的答案但面试时把这个思路说出来能体现你的数感。6. 真实面试中的追问拆解与答题节奏建议6.1 那些容易让代码出错的细节这道题提交出错率很高的点集中在三个地方初始化值选择不当amount 1在有超大面额硬币时依然安全但有些人用Integer.MAX_VALUE在Java里再加1直接溢出成负数dp数组就被污染了。对“无解”状态的判断不统一。递归版返回值里既有无解标志又有实际值容易把无解误当0。忘记把Infinity初始值做最终判断直接返回dp[amount]导致无解时输出 Infinity 而不是 -1。这些都在真实面试中出现过。最稳的检查方式就是写完代码后口头报一遍复杂度再用两个边界例子在纸上过一遍。6.2 五个高频追问和应对思路追问方向应对思路硬币数量有限怎么办属于多重背包可拆成01背包处理或用二进制优化amount非常大怎么办先把coins排序优先尝试大面额剪枝也可先算gcd判断无解能不能用BFS做能。把amount看作状态每次减一枚硬币找最短路径。状态空间小时可行要求输出最少方案组合加parent数组回溯见上一节实现如果硬币面额为小数呢先整体乘10的幂次转成整数再做或改用精度更高的处理思路其中BFS这个点值得多说一句零钱兑换求“最少硬币数”本质是在一张隐式状态图上做最短路。每个状态是金额边是硬币面额。BFS从amount出发向外扩展第一次到达0时的层数就是答案。这种方法在某些硬币面额宽泛的场景里思路直观但状态可能很多空间消耗比DP大。6.3 一个可以复刻的答题节奏结合我自己的经验面试中的标准话术可以这样组织先说“这题可以抽象成找最少的组合数量”顺便确认硬币是否无限、是否必须恰好凑齐。举一个贪心失败的反例表明这不是贪心题。说暴力递归版本简单画一下递归树指出重叠子问题。加上memo改成自顶向下。再进一步改成自底向上的一维DP写出代码说清复杂度 O(amount * n)。在面试官感兴趣的情况下展示parent数组输出路径并对比518题的组合数写法。上面这套流程走下来一个问题变成了四五层递进面试官能得到的信息量远超“他会不会做这一题”。我实际参与面试时最满意的候选人恰恰不是秒写出标准解的人而是能把暴力解和优化解串成一条线讲清楚的人。最后说点个人体会零钱兑换这道题的真正价值不在于让你记住一个方程而是让你理解“为什么暴力解会重复计算”“为什么用空间能换时间”“为什么同样是动态规划遍历顺序会导致完全不同的语义”。把这几个点想透以后看到斐波那契、爬楼梯、编辑距离甚至背包问题都会有一种“原来都是在同一个框架里”的感觉。面试前与其被模板不如把这道题自己从头推一遍用嘴讲一遍。能讲通考场上就稳了。