企业官网建设流程全解析

刷 LeetCode 的人应该都遇到过 322 这道题，零钱兑换，算得上是动态规划里最经典的入门题目之一。面试考它的频率也相当高，因为题目本身不复杂，但背后能延伸出的东西很多：状态定义、递推方向、边界初始化、以及后续的一堆变体。如果你现在做题看答案能看懂，但自己写的时候总是卡住，尤其是不知道 dp 数组初始值为什么要设成 amount + 1，或者为什么先遍历硬币和先遍历金额结果完全不一样，那这篇文章就是给你准备的。

这道题适合所有正在系统刷题的人，无论你刚开始学动态规划，还是已经刷了几百题想回来加固基础，它都值得再认真看一遍。我尽量用最直白的话把它拆开，从最开始的思路分析，到代码实现，再到那些容易被忽略的细节和面试官爱追问的变体，一次说透。

1. 题目拆解与核心思路

1.1 题目到底在说什么

先看一下题目描述，其实非常简短：给你一个整数数组 coins，表示不同面额的硬币，以及一个整数 amount 表示总金额。你要计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。

关键信息有三个：硬币面额是给定的、每种硬币可以无限用、问的是最少数量的组合。第一眼看上去很容易想到贪心，但实际刷过的人都知道，这道题用贪心是过不掉的。原因也很简单，贪心策略是“每次尽量用大面额的硬币”，这个策略只有在某些特殊货币体系下才成立，比如人民币的面额设计，1、2、5、10 这些面额之间相互整除，贪心确实能得到最优解。但 LeetCode 的测试数据不保证这个性质。

举个例子，coins = [1, 3, 4]，amount = 6。如果按贪心来做，先用面额 4 的硬币，剩下 2，只能用两个 1，总硬币数是 3。但实际上最优解是两个 3，硬币数是 2。差距直接出来了。所以这题不能用贪心，得用动态规划。

1.2 为什么动态规划能解决这个问题

动态规划的核心思想是把一个大问题拆成很多有重叠的小问题，然后从小问题的答案一步步推到大问题。

对于零钱兑换来说，我要算凑出金额 amount 需要的最少硬币数，那我可以反过来想：如果我最后选择了一枚面额为 c 的硬币，那么问题就变成了凑出 amount - c 需要的最少硬币数，再加上这枚硬币就是当前方案的硬币数。我只需要枚举所有可能的 c，取最小的那个结果就行。

这其实就是状态转移的本质。你把“凑出金额 x 的最少硬币数”定义为一个状态，记为 f(x)，那么：

f(x) = min(f(x - c1), f(x - c2), ..., f(x - cn)) + 1

其中 c1 到 cn 是 coins 数组里的所有面额，并且要求 x - ci >= 0。这个方程看起来简单，但它是整个题目的灵魂。只要想清楚这个递推关系，代码就是按这个公式来的。

这里面有个很重要的直觉，就是“每一步只关心最后一枚硬币选谁”。因为硬币可以无限用，前面不管怎么选，都不会影响后面还能不能继续选某种面额。这种“只考虑当前这一步，剩下的交给子问题”的思维方式，就是动态规划的核心。

1.3 两种实现方向：记忆化搜索 vs 自底向上

同样的递推方程，有两种写法：自顶向下和自底向上。

自顶向下就是从 amount 开始，递归地向下计算 f(amount - c)，同时用一个备忘录数组记录已经算过的结果，避免重复计算。这个写法的好处是符合人类思考习惯，不需要想清楚完整的 dp 表格结构，缺点是递归层数受限于 amount，而且在一些平台上递归效率略低。

自底向上就是直接从 f(0)、f(1) 开始往上推，用一个 dp 数组存结果，dp[i] 表示凑出金额 i 需要的最少硬币数，从 i = 1 循环到 i = amount，每次枚举硬币面额。这个写法更通用，也更容易和其他背包类问题衔接，所以我个人比较推荐在面试中先展示这种写法。

两种方法的时间复杂度理论上是相同的，都是 O(amount * n)，n 是硬币种类数，空间都是 O(amount)。区别只是计算顺序。记忆化搜索是“用到哪个算哪个”，自底向上是“全都算一遍”，但本质上没有谁优谁劣。

2. 方法一：自顶向下记忆化搜索

2.1 状态定义与递归方程

自顶向下写法的核心，就是定义一个递归函数 f(remain)，表示凑出剩余金额 remain 需要的最少硬币数。如果 remain 正好是 0，说明不需要任何硬币，返回 0。如果 remain 小于 0，说明当前这个选择已经失败了，返回一个负数或者无穷大，具体要看你怎么处理。

递推关系就是遍历每一枚硬币 c，如果 remain - c >= 0，就递归计算 f(remain - c) + 1，然后取所有结果的最小值。这里最容易出问题的地方，就是“返回什么表示无解”。我见过很多人在递归里面返回 -1 表示无解，然后在外面判断 +1 之后的结果要额外处理，写法非常别扭。

建议你这样设计：如果当前状态没有任何硬币可选，说明这条路走不通，直接返回一个很大的数，比如 Integer.MAX_VALUE / 2，这样外层取 min 的时候自动忽略它。最后如果结果还是那个很大的数，就代表无解，返回 -1。

2.2 备忘录的剪枝作用

如果只是傻递归，复杂度是指数级的，因为每个状态都会不断展开成很多子状态，而且不同的路径会到达同一个状态。比如 coins = [1, 2, 3]，在一个递归过程中，先减 1 再减 2，和先减 2 再减 1，最终都到达同一个 remain。如果没有备忘录，这两条路径都会被完整计算一遍，浪费就大了。

备忘录数组 memo 的长度设为 amount + 1，初始值是 0。memo[i] 不为 0 就表示已经算过并保存了结果，直接返回。如果你要保存的结果可能是 0，那就得用 -1 表示“未计算”，或者用一个布尔数组单独标记。

我在实际写的时候，更习惯用 Integer.MAX_VALUE / 2 作为无解的标识，而不是用 -1。原因很简单，-1 在判断最小值的时候会干扰逻辑。举个例子，如果你在递归里返回 -1 表示无解，外层看到 -1 还得判断“哦这是无解，不能参与 min 计算”，代码会多出很多 if。而用一个足够大的正数，min 天然就会忽略它。

2.3 代码实现

直接看代码，我用的伪 Java 风格，思路清楚了其他语言都能套：

class Solution { int[] memo; int[] coins; public int coinChange(int[] coins, int amount) { this.coins = coins; memo = new int[amount + 1]; Arrays.fill(memo, -1); // -1 表示还没有计算过 int ans = dfs(amount); return ans >= Integer.MAX_VALUE / 2 ? -1 : ans; } private int dfs(int remain) { if (remain < 0) return Integer.MAX_VALUE / 2; if (remain == 0) return 0; if (memo[remain] != -1) return memo[remain]; int res = Integer.MAX_VALUE / 2; for (int c : coins) { res = Math.min(res, dfs(remain - c) + 1); } memo[remain] = res; return res; } }

这里面有几点要解释一下。首先，remain 小于 0 时返回一个很大的数，是因为递归调用 dfs(remain - c) 可能产生负数。你当然可以在调用前先判断 remain >= c，但那样会多写一个 if。直接在入口处统一处理，代码更干净。

其次，res 的初始值也是一个大数，它会保证最终 memo[remain] 的语义是“凑出 remain 所需的最少硬币数；如果无法凑出，就等于这个很大的数”。

这个写法我在自己的模拟项目里用过很多次，遇到递归类 DP 问题都挺顺手。唯一的缺点是递归深度。如果 amount 是 10 的 4 次方级别，递归深度可能上万，Java 默认栈会爆。LeetCode 上这道题 amount 最大是 10 的 4 次方，理论上自顶向下在某些极端数据下有栈溢出的风险。所以保险起见，面试的时候我更推荐下面这种自底向上写法。

3. 方法二：自底向上动态规划

3.1 状态定义和转移方程推导

自底向上的思路更符合“填表格”这个直觉。还是那个 dp 数组，dp[i] 表示凑出金额 i 需要的最少硬币数。你从 dp[0] 开始，dp[0] = 0，表示凑 0 块钱不用任何硬币。然后从 i = 1 循环到 i = amount，逐个计算 dp[i]。

计算 dp[i] 的时候，你遍历每一枚硬币 c，如果 i >= c，那么 dp[i] 就可能等于 dp[i - c] + 1。这里 dp[i - c] 已经算好了，因为你从小到大循环，i - c 肯定小于 i。取所有可能值里的最小值即可。

转移方程写出来就是：

dp[i] = min(dp[i], dp[i - c] + 1)，对于所有 c <= i

你可以发现，这其实就是把递归反过来。递归是从大往小走，到边界再回来；自底向上是从小往大推，直接用已算出的结果。两种方法对应的思考路径完全不同，但最终代码的效果一样。

3.2 初始化：dp[0] = 0，其余用 amount + 1

这是新手最容易卡住的地方。为什么 dp 数组不初始化为 0？因为 dp[i] 要存“最少硬币数”，初始化为 0 的话，min 比较的时候永远会留下 0，结果就全错了。所以你一定要把 dp[i] 初始化成一个对当前场景来说“特别大”的数，这样它在被真实计算结果覆盖之前，不会污染最小值。

这个“特别大”的数是多少？有人用 Integer.MAX_VALUE，有人用 amount + 1。我建议用 amount + 1，原因有两个。第一，如果这个金额真的可以被凑出来，硬币数最多不会超过 amount（最小面额是 1 的时候，硬币数最多正好是 amount），所以 amount + 1 一定能保证比任何真实解都大。第二，Integer.MAX_VALUE 在 dp[i - c] + 1 的时候可能溢出，变成负数，造成隐蔽的 bug。用 amount + 1 就完全没这个问题，因为 dp[i - c] 最大也就 amount + 1，加 1 之后是 amount + 2，也不会溢出。

提示：这是一个很多人会踩的坑。如果 dp 数组初始化为 Integer.MAX_VALUE，且你忘了在加 1 前判断一下 dp[i - c] 是否可到达，某次计算就可能溢出成负数，然后整个逻辑全乱掉。amount + 1 这种初始化方式能直接避免这个问题。

3.3 核心代码实现

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int c : coins) { if (c <= i) { dp[i] = Math.min(dp[i], dp[i - c] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } }

这段代码很短，但信息量不小。外层循环遍历金额，内层循环遍历硬币，这时候你会发现一个有趣的现象：如果外层遍历硬币、内层遍历金额，代码还能正确吗？答案是对于这题来说，还是正确的，但循环顺序背后其实是有讲究的。因为 dp[i - c] 只要小于 i 就是已经算好的状态，与循环顺序无关，所以两种写法都行。后面到组合总数问题的时候，内外循环顺序就成了决定“能不能重复使用硬币”的关键，到时候我们再细说。

返回值判断也很有意思：dp[amount] 如果还是 amount + 1，说明它从来没被任何硬币组合更新过，也就是无解，返回 -1。

3.4 复杂度与空间优化分析

时间复杂度是 O(amount * n)，因为两层循环，外层 amount 次，内层 coins.length 次，每次都是常数时间操作。空间复杂度是 O(amount)，因为只开了一个长度为 amount + 1 的数组。

有些人会问，这里能不能像零钱兑换 II 那样用一维数组压缩，是不是已经是一维了？对，这个 DP 本身就是一维的，因为问题的状态只跟金额有关，不需要记录“用了哪几种硬币”。但如果你扩展一下，把限制改成“每种硬币只能用一次”，那状态就得多一维，变成经典的 0-1 背包问题，这时候 dp 数组的更新顺序就非常重要了。

至于能不能继续优化空间到 O(1)？这题做不到，因为金额 amount 是输入的参数，你至少需要 O(amount) 的空间来记录每个金额的结果。除非你只想求某个特定金额，但那样也得用记忆化递归。目前这个解法已经是这题的空间最优解之一。

4. 常见细节与易错点

4.1 为什么 dp[i] 的最小硬币数一定可以用 amount + 1 来兜底

这个问题值得再说一次，因为面试真的会问。

假设存在一种组合可以凑出金额 i，那么组成这种组合的硬币数量至少是 1。所有硬币的面额最小也是 1，所以如果你全用面额 1 的硬币，凑出 i 需要 i 枚硬币。即使硬币面额里有 1，那最多也就是 i 枚；如果硬币面额里没有 1，那硬币数只会更少，不会更多。因此，任何可达状态的硬币数都不会超过 amount 本身。于是把初始值设成 amount + 1，就保证它永远大于任何真实解。

那如果某金额不可达，dp 的值就保留为 amount + 1，不会被任何路径更新掉。最后判断 dp[amount] 是否大于 amount 就能识别无解。这个设计是这道题的一个经典技巧，面试官很爱追问“为什么是 amount + 1 不是 Integer.MAX_VALUE”，答清楚这个，印象分会好很多。

4.2 边界情况：amount 为 0 或 coins 数组为空

先看 amount = 0，题目要求凑出金额 0，什么都不用做就是 0 枚硬币，所以返回 0。上面的代码完全不需要特殊处理，因为 dp[0] = 0，循环从 i = 1 开始，根本进不去，最后返回 dp[0] = 0。

再看 coins 数组为空的情况。其实这种测试数据一般不会出现，但如果出现了，上面的代码也能兜住：内层循环直接不执行，dp[1] 到 dp[amount] 全是 amount + 1，最后返回 -1，符合“没法凑”的语义。不过严格说，题目给的 coins 长度至少为 1，这里只是说明代码有容错性。

还有 amount 是负数的情况，题目不会给，如果真遇到了，你想返回 0 或 -1 都可以，但通常不会成为考虑场景。

4.3 极端用例在本题的分布

LeetCode 的数据里有一批大数用例，比如 coins 里只有一个面额很大的硬币，amount 又很小。这种用例主要考验的是代码会不会越界，以及在无解场景下能不能正确返回 -1。比如 coins = [2]，amount = 3，唯一的硬币面额是 2，永远凑不出 3。代码里的 dp[3] 会一直保持 4（amount + 1），最后返回 -1，正确。

还有一种极端是 amount 非常大，比如 10 的 4 次方，coins.length 也很大。两层循环的常数可能有点高，但 LeetCode 的时限足够宽，正常写都能过。如果你遇到超时，可以先考虑排序剪枝，比如从大面额开始枚举，这样能更早逼近可行区间，但最坏复杂度不变。

5. 面试场景与变体拓展

5.1 面试时怎么讲思路才加分

这道题在面试里出现频率很高，但很多人一上来就写状态转移方程，面试官可能还没跟上。正确的讲法应该是分三步走。

第一步，先讲“我一开始可能会想贪心”，然后主动举一个反例把它推翻。比如 coins = [1, 3, 4]，amount = 6，贪心得到 3 枚，最优是 2 枚，所以这道题必须考虑全局最优解。

第二步，引出动态规划的重叠子问题。你说“如果我知道凑出 5 块钱需要几枚硬币，那凑 6 块钱就可能是凑 5 再加一枚 1 块”，这个思路面试官很容易接受。

第三步，再给出状态定义、转移方程、初始化和复杂度。这样从直觉到抽象，逻辑完整，面试官会觉得你不只是在背答案，而是真的理解。

5.2 变体一：打印具体的硬币组合

如果面试官往深问，最常见的变体就是“我不要最少硬币数，我要你把具体组合打印出来”。这个改动其实很小，你只需要额外维护一个数组 pre[i]，记录 dp[i] 是从哪个金额转移过来的。

具体做法是，每次更新 dp[i] 的时候，同步记录 pre[i] = i - c，也就是上一步的金额。算完之后，从 amount 开始，不断根据 pre 数组回退，直到走到 0，期间每个差值就是一选择的一枚硬币面额。

举个例子，amount = 6，coins = [1, 3, 4]。最优解是 3 + 3，dp[6] 可能由 dp[3] 转移而来，pre[6] = 3，然后 dp[3] 由 dp[0] 转移，pre[3] = 0。回溯的过程就是 6 -> 3 -> 0，对应的硬币就是 3 和 3。

这种路径回溯在面试中是个很好的加分项，说明你对动态规划不仅有“求最值”的理解，还有“跟踪解”的能力。类似的技巧在很多题目里都会用到，比如最长上升子序列的输出。

5.3 变体二：求组合总数（零钱兑换 II）

这是最经典的衍生题，题目描述变成了“多少种不同的组合方式可以凑出指定金额”，而不是最少硬币数。这题的解法还是动态规划，但细节变化非常大。

如果沿用这题的转移方程，只是把 min 改成 sum，那会有个严重问题：同样的硬币组合会因为排列顺序不同被重复计数。比如 coins = [1, 2]，amount = 3，组合可以是 1 + 1 + 1、1 + 2、2 + 1。变成求和的话，1 + 2 和 2 + 1 会被当成两种。

这时候就是内外循环顺序的经典考点。如果你想求的是组合数，不关心顺序，那应该外层遍历硬币、内层遍历金额。这样每个硬币只会被“按顺序”使用，不会出现先选 1 再选 2 和先选 2 再选 1 同时被计数的现象。而这个顺序在本篇的零钱兑换里无关紧要，因为只求最少数量，重复排列不会影响最小值。

所以你会发现，同一个 DP 框架，换一个循环顺序，整个题目的语义就变了。这个知识点我在面试中遇到过很多次，属于高频考点中的高频。

5.4 变体三：每种硬币有使用次数限制

如果题目改成“每种硬币最多可以用 k 次”，那这就是多重背包问题。解决办法是把每个面额拆成若干个“绑定套装”，然后用 0-1 背包的思路来做，或者用二进制拆分优化复杂度。

二进制拆分是其中比较重要的技巧。比如某种硬币最多能用 10 次，你可以拆成 1、2、4、3 这样的组，这些组能组合出 0 到 10 的所有整数。原来要枚举 10 次，现在只要枚举 4 次，复杂度从 O(amount * n * k) 降到了 O(amount * n * log k)。这个技巧在很多背包类问题里都能用，拓宽思路的时候很值得了解一下。

了解这些变体不是为了死记硬背，而是为了让你看到动态规划里“状态定义决定了一类题”的规律。同一道题目把目标函数改一改，限制条件加一加，解法就完全变了。理解这些变化的根源，刷题效率会高很多。

6. 实测体会与刷题建议

6.1 刷这道题最容易出现的三个错误

我在实际带人刷题的过程中，发现三个高频错误。第一是把 dp 数组初始化为 0，然后 min 比较永远取 0，导致结果全错。这个错误本质是没想清楚“不可达状态用 0 来表示并不合适”，因为 0 本身可能是合法结果，这个语义就冲突了。

第二是在自顶向下的递归里，用 -1 表示无解，然后在返回值处理上写一堆判断，代码难看且容易漏判。第三个错误是把 dp[i] 的更新写成 dp[i] = Math.min(dp[i - c], dp[i]) + 1，注意这里加 1 的位置不能乱放。正确写法是 dp[i] = Math.min(dp[i], dp[i - c] + 1)，如果你把加 1 放到括号外面，逻辑就变成了“先忽略当前硬币，对之前的 dp[i - c] 加 1”，这是错的，因为 dp[i - c] 表示的已经是凑出 i - c 的完整结果，再加 1 才表示加上当前硬币。

6.2 从这道题延伸出去的学习路线

零钱兑换这道题看起来小，但它跟很多题是相通的。你把它吃透了，再去看完全背包、0-1 背包、多重背包，会发现自己已经懂了一大半。因为这个问题的状态定义、初始化、转移、复杂度分析，就是背包问题的一个缩影。

我的建议是，刷完这道题之后，立刻做这几件事。首先，把自顶向下和自底向上两种写法都独立写一遍，不要只是复制粘贴。其次，做一下零钱兑换 II，体会循环顺序对“排列数还是组合数”的影响。最后，如果你的精力够，试试看能不能自己把路径打印出来，再自己改成限制硬币数量的情况。这几件事做完，这道题才算真正消化了。

6.3 我在实际刷题中的一些心得

说点个人体会。我记得自己刚开始刷 DP 的时候，也在这道题上卡了好一阵，问题不在代码，而在思维方式。我一直试图用一个“统一的公式”去套所有动态规划，后来才发现动态规划的关键不是公式，而是状态定义。状态定义好了，转移方程就是顺水推舟的事。

所以如果你想提高 DP 水平，我不建议直接背这题的模板，而是建议每次做题前先花一分钟想清楚三件事：第一，我的状态是什么；第二，我要怎么表示“不可达”；第三，我从小到大计算是否满足依赖关系。这三个问题想清楚，大部分基础 DP 题都不难。

另一个小技巧是，调试动态规划题目的时候，可以自己写一个打印 dp 数组的小工具，把每一轮的值打印出来。用眼睛看一遍 dp 数组的变化，比在脑子里模拟快得多。尤其是状态太多、转移复杂的题目，打印中间结果几乎是最有效的排查手段。零钱兑换这个题的 dp 数组不大，打印出来观察一次，你对“状态转移到底是怎么发生的”会有一个非常直观的感受。