企业官网建设流程全解析

零钱兑换这道题，我在实际面试和帮人模拟面试里见过太多次了。不少人能背出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 变成 2（1 + 2），dp[4]从 4 变成 2（2 + 2），一步步优化上去。

用硬币5更新后，dp[5]从 5 变成 1（直接用1枚5元硬币），dp[6]从 6 变成 2（1 + 5），dp[10]从2变成2（5+5也是2），dp[11]最终是 3（5+5+1）。

手推一次你会明显感觉到：这个表的每一格，都是在“上一次最优解”的基础上，拿一枚新硬币去碰。碰得更优就更新，碰不动就保持原状。

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，返回 0
• coins = [2]，amount = 3，返回 -1
• coins = [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) = 2，2不能整除5，直接返回 -1。这种剪枝在实际比赛中作用不大，因为DP本身也能算出同样的答案，但面试时把这个思路说出来，能体现你的数感。

6. 真实面试中的追问拆解与答题节奏建议

6.1 那些容易让代码出错的细节

这道题提交出错率很高的点，集中在三个地方：

• 初始化值选择不当，amount + 1在有超大面额硬币时依然安全，但有些人用Integer.MAX_VALUE，在Java里再加1直接溢出成负数，dp数组就被污染了。
• 对“无解”状态的判断不统一。递归版返回值里既有无解标志又有实际值，容易把无解误当0。
• 忘记把Infinity初始值做最终判断，直接返回dp[amount]，导致无解时输出 Infinity 而不是 -1。

这些都在真实面试中出现过。最稳的检查方式就是：写完代码后，口头报一遍复杂度，再用两个边界例子在纸上过一遍。

6.2 五个高频追问和应对思路

其中BFS这个点值得多说一句：零钱兑换求“最少硬币数”，本质是在一张隐式状态图上做最短路。每个状态是金额，边是硬币面额。BFS从amount出发向外扩展，第一次到达0时的层数就是答案。这种方法在某些硬币面额宽泛的场景里思路直观，但状态可能很多，空间消耗比DP大。

6.3 一个可以复刻的答题节奏

结合我自己的经验，面试中的标准话术可以这样组织：

1. 先说“这题可以抽象成找最少的组合数量”，顺便确认硬币是否无限、是否必须恰好凑齐。
2. 举一个贪心失败的反例，表明这不是贪心题。
3. 说暴力递归版本，简单画一下递归树，指出重叠子问题。
4. 加上memo改成自顶向下。
5. 再进一步改成自底向上的一维DP，写出代码，说清复杂度 O(amount * n)。
6. 在面试官感兴趣的情况下，展示parent数组输出路径，并对比518题的组合数写法。

上面这套流程走下来，一个问题变成了四五层递进，面试官能得到的信息量远超“他会不会做这一题”。我实际参与面试时，最满意的候选人恰恰不是秒写出标准解的人，而是能把暴力解和优化解串成一条线讲清楚的人。

最后说点个人体会：零钱兑换这道题的真正价值不在于让你记住一个方程，而是让你理解“为什么暴力解会重复计算”“为什么用空间能换时间”“为什么同样是动态规划，遍历顺序会导致完全不同的语义”。把这几个点想透，以后看到斐波那契、爬楼梯、编辑距离，甚至背包问题，都会有一种“原来都是在同一个框架里”的感觉。面试前与其被模板，不如把这道题自己从头推一遍，用嘴讲一遍。能讲通，考场上就稳了。