零钱兑换全解析：动态规划状态转移方程与dp数组初始化详解

1. 这道题的真正考点：你为什么需要读懂题面背后的意思

先把这个高频题放在一个更实际的场景里看。我们每天都在遇到"找零"这件事：假设你手头有几种固定面额的硬币，比如1元、2元、5元，现在要凑出11元，问最少用几枚硬币。钱够不够、凑不凑得出来，这是另一回事；在有解的前提下，硬币数量越少越好。

力扣322题"零钱兑换"就是把这件事抽象成了一个纯数学问题：给定一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额，计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

我第一次刷这道题的时候，第一反应是"这题不是挺简单的吗，每次先用最大面额去凑不就行了"——这就是典型的贪心思维。但很快就会被一个反例打脸。

典型反例：coins = [1, 3, 4]，amount = 6。贪心策略会先选4，剩2，只能选1+1，总共3枚硬币。但最优解是3+3，只要2枚。贪心在这里完全失效。

这个反例就是这道题的核心价值所在：它逼着你从"局部最优"跳到"全局最优"，也就是动态规划。对于正在准备算法面试的开发者来说，这题是理解动态规划的入门必刷题，它几乎把动态规划的几个核心要素——状态定义、状态转移方程、边界条件、结果判断——全部覆盖了。适合刚接触动态规划的初学者，也适合想在面试前快速过一遍高频题的求职者。

2. 核心思路拆解：状态定义、状态转移方程与初始化为什么会是这样

2.1 从"凑金额"到"拆子问题"的思考路径

动态规划的核心思路是"大事化小"。你要凑 amount，可以先想想"凑 amount 之前最后一步用了哪枚硬币"。如果最后一枚硬币面额是 coin，那么在用到这枚硬币之前，你需要凑的金额就是 amount - coin。

这样一来，"凑 amount 需要的最少硬币数"就可以由"凑 amount - coin 需要的最少硬币数 + 1"推导出来。你只需要遍历所有可能的 coin，取其中最小的那个结果。

这个思路能成立的前提是：子问题之间互相独立。也就是说，凑 amount - coin 的最优解不会因为"你最后选了一枚 coin"而发生改变。在实际场景里，这等价于"硬币可以无限次使用"，所以子问题之间确实不会互相干扰。这正是这道题能用动态规划的原因。

这里需要引入两个状态定义。我直接用最常见的定义方式：设 dp[i] 表示凑成金额 i 所需的最少硬币数。那么 dp[amount] 就是题目要求的答案。这个定义非常自然，因为它把"原问题"直接映射成了"数组中的一个值"。

2.2 状态转移方程是怎么推出来的

有了 dp[i] 的定义，状态转移就不难写了。对于每一个金额 i，遍历所有硬币面额 coin：

• 如果 coin 小于等于 i，说明这枚硬币可以被放进组合里；
• 在放这枚硬币之前，要凑的金额是 i - coin，对应的最少硬币数是 dp[i - coin]；
• 放完这枚硬币之后，总硬币数是 dp[i - coin] + 1。

所以：

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

这个方程的意思是：要么保持当前的 dp[i] 不变（也就是不使用这枚 coin），要么尝试一下"先凑 i - coin，再加上这枚 coin"的方案，两者取最小值。

我把这个转移过程类比成日常点外卖：假设你预算有限，每一家店的配送费固定，你要用最少的订单数把预算花完。每下一单之前，你都要看看"剩余预算最少要下几单"，然后选择让总订单数最少的那个方案。这里的"剩余预算"就是 i - coin，"最少要下几单"就是 dp[i - coin]，"加上当前这一单"就是 +1。

2.3 初始化为什么用 amount + 1 而不是一个很大的数

dp 数组的初始值设置，是这道题最容易出问题的地方之一。我见过不少初学者把 dp[i] 初始化为 Integer.MAX_VALUE，然后转移的时候直接做 dp[i - coin] + 1 的加法，结果一加就爆了，变成了负数，整个 dp 逻辑直接崩掉。

比较稳妥的做法是把 dp[i] 初始化为amount + 1。为什么是这个数？

因为凑成金额 i 最多只会用到 i 枚硬币（全部用面额为1的硬币，且假设存在面额为1的硬币）。即使存在面额为1的硬币，dp[i] 的最大值也不会超过 i，更不会超过 amount + 1。所以用 amount + 1 作为"无穷大"的替代值，既保证了逻辑上"没有被更新过"的语义，又避免了加法溢出的风险。

在具体实现时，需要注意一个对称的边界条件：dp[0] 必须是 0。金额为0时，不需要任何硬币，这是一个空组合。如果你把 dp[0] 初始化为 amount + 1，后面所有的转移都会出错，因为任何金额 i 都会尝试从 dp[0] + 1 取解。

这个细节印证了动态规划的一个通用原则：初始化不是随便填个数，初始化的值必须能参与状态转移，并且保证转移后的结果是正确的。

3. 实操实现细节：两种经典写法的完整代码与选择建议

3.1 自底向上的迭代写法（推荐优先掌握）

我先把最推荐、也最符合大部分人直觉的写法贴出来。我用 Python 写，因为这个版本在面试现场最好读、最好改：

def coinChange(coins, amount): # 初始化 dp 数组，长度为 amount + 1 # 每个位置先赋予一个"不可能达到"的上界值 dp = [amount + 1] * (amount + 1) dp[0] = 0 # 凑 0 元不需要硬币 # 从 1 开始逐一计算凑到每个金额的最少硬币数 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) # 如果 dp[amount] 仍然是初始值，说明无法凑出该金额 return dp[amount] if dp[amount] != amount + 1 else -1

这段代码的核心只有三个部分：初始化、双层循环状态转移、结果判断。你可能会问：外层循环为什么从1开始，而不是从0开始？因为 dp[0] 已经初始化好了，可以直接省略这轮计算。内层循环就是遍历所有硬币，只要 coin 不大于当前金额 i，就尝试转移。

顺便说一下，如果你想让内层循环更高效一点，可以提前把 coins 排序。排序之后，一旦碰到 coin > i，后面的硬币面额只会更大，直接 break 跳出内层循环，就不需要继续遍历了。

def coinChange(coins, amount): coins.sort() # 预处理，让剪枝成为可能 dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin > i: break dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1

3.2 自顶向下的记忆化搜索：另一种思路与取舍逻辑

如果你觉得迭代法不好理解，可以试试记忆化搜索。它的递归逻辑更贴近人类直觉：我要凑 amount，就递归地去问"先选一枚硬币，然后在剩余金额上递归"，同时用一个 memo 数组记录已经算过的子问题，避免重复计算。

def coinChange(coins, amount): memo = [-1] * (amount + 1) def dfs(rem): # 递归到 0，表示恰好凑完，不需要再选硬币 if rem == 0: return 0 # 负数表示当前路径凑过了，属于无效分支 if rem < 0: return -1 # 这个子问题已经计算过，直接取答案 if memo[rem] != -1: return memo[rem] ans = float('inf') for coin in coins: sub = dfs(rem - coin) if sub != -1: ans = min(ans, sub + 1) memo[rem] = ans if ans != float('inf') else -1 return memo[rem] return dfs(amount)

这两种写法的本质是一样的，区别只在于遍历方向。迭代法是"从小金额往大金额推"，记忆化搜索是"从大金额往小金额递归，再回溯回去"。我对初学者的建议是：先把迭代法背熟，因为它的空间复杂度更容易分析，也更容易在纸上手动模拟；等对动态规划熟悉之后，再尝试理解记忆化搜索的递归思路，两种方法可以互相验证。

3.3 补充一段 C++ 实现，方便对比语言差异

有些读者习惯用 C++ 刷题，我也补一段参考代码。注意 C++ 的 vector 初始化和 Python 的列表初始化语法不同，但核心逻辑完全一致：

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int coin : coins) { if (coin <= i) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } };

C++ 版本注意两点：一是 dp[amount] > amount 的判断，因为如果无解，dp[amount] 会保持初始值 amount + 1，这个值必然大于 amount；二是因为初始值 amount + 1 并不是很大的数，min操作完全安全，不会出现溢出问题。

4. 过程推导：手把手把 dp 数组跑一遍

4.1 以 coins = [1, 2, 5]，amount = 11 为例

光讲理论还是有点抽象，我建议你拿纸笔跟我一起跑一遍。这是理解动态规划最笨但也最有效的方法。

先初始化 dp 数组：长度是 amount + 1 = 12，下标从 0 到 11。dp[0] = 0，其余都初始化为 11 + 1 = 12。

• i = 1：遍历硬币。coin=1 时，dp[1]=min(12, dp[0]+1)=1；coin=2 和 5 都大于1，跳过。所以 dp[1]=1。含义：凑1元用1枚1元硬币。
• i = 2：coin=1，dp[2]=min(12, dp[1]+1)=2；coin=2，dp[2]=min(2, dp[0]+1)=1。所以 dp[2]=1。凑2元可以用1枚2元硬币。
• i = 3：coin=1，dp[3]=min(12, dp[2]+1)=2；coin=2，dp[3]=min(2, dp[1]+1)=2。所以 dp[3]=2（1+2）。
• i = 4：coin=1，dp[4]=min(12, dp[3]+1)=3；coin=2，dp[4]=min(3, dp[2]+1)=2。所以 dp[4]=2（2+2）。
• i = 5：coin=1，dp[5]=min(12, dp[4]+1)=3；coin=2，dp[5]=min(3, dp[3]+1)=3；coin=5，dp[5]=min(3, dp[0]+1)=1。所以 dp[5]=1（1枚5元硬币）。
• i = 6：coin=1，dp[6]=min(12, dp[5]+1)=2；coin=2，dp[6]=min(2, dp[4]+1)=3，min后还是2；coin=5，dp[6]=min(2, dp[1]+1)=2。所以 dp[6]=2（5+1）。
• i = 7：coin=1，dp[7]=min(12, dp[6]+1)=3；coin=2，dp[7]=min(3, dp[5]+1)=2；coin=5，dp[7]=min(2, dp[2]+1)=2。所以 dp[7]=2（5+2或者2+5）。
• i = 8：coin=1，dp[8]=min(12, dp[7]+1)=3；coin=2，dp[8]=min(3, dp[6]+1)=3；coin=5，dp[8]=min(3, dp[3]+1)=3。所以 dp[8]=3。
• i = 9：coin=1，dp[9]=min(12, dp[8]+1)=4；coin=2，dp[9]=min(4, dp[7]+1)=3；coin=5，dp[9]=min(3, dp[4]+1)=3。所以 dp[9]=3。
• i = 10：coin=1，dp[10]=min(12, dp[9]+1)=4；coin=2，dp[10]=min(4, dp[8]+1)=4；coin=5，dp[10]=min(4, dp[5]+1)=2。所以 dp[10]=2（5+5）。
• i = 11：coin=1，dp[11]=min(12, dp[10]+1)=3；coin=2，dp[11]=min(3, dp[9]+1)=4；coin=5，dp[11]=min(3, dp[6]+1)=3。所以 dp[11]=3。

最终答案就是 dp[11] = 3，对应的最优组合是 5+5+1。这个手动推导过程有一个很明显的特征：每一个 dp[i] 只依赖比它更小的 dp 值，而比它小的 dp 值在前面已经严格计算好了。这正是"自底向上"的含义。

4.2 复杂度分析与空间优化思路

时间复杂度：外层循环跑 amount 次，内层循环跑 coins 的长度 n 次，所以总复杂度是 O(amount × n)。这个复杂度对于 amount 不太大的场景是可以接受的。空间复杂度是 O(amount)，因为只用了一个一维数组。

如果你对空间有进一步要求，能不能只用几个变量来滚动更新？在这个问题里是不行的。因为 dp[i] 依赖的是任意 dp[i - coin]，而 coin 可以是任意面额，等于说 dp[i] 依赖的是前面所有位置的值，而不是只依赖前一个或前两个值。所以一维数组是最低的空间要求，没法再压缩成常数级。

不过这里有一个可以讨论的点：如果改成"每种硬币只能用一次"，那就是 0-1 背包问题，复杂度分析和滚动数组的思路又不一样了。我在实际面试中遇到面试官追问"能不能空间优化"时，都会先明确一点：322 这题本身已经是一维 dp，空间优化空间不大；面试官更想考察的是你对状态定义的理解，而不是花式压缩空间。

4.3 边界条件与无解判断的底层逻辑

边界条件在这里非常关键。主要有三个：

• amount = 0：返回 0。因为凑0元不需要任何硬币。这在 dp 初始化中已经处理了，所以在代码开头不需要额外写 if 判断，但面试时要说清楚。
• coins 包含面额为0的硬币？题目描述中通常不会出现这种情况，但如果你写代码时会遇到 dp[i - 0] 就是 dp[i] 本身，会导致转移方程产生自循环。实际刷题不用考虑这个极端情况，面试时可以和面试官确认一下。
• 无解：比如 coins = [3]，amount = 2，dp[2] 无法被更新，仍然是初始值 amount + 1 = 3。此时返回 -1。

无解判断的底层逻辑是：如果某个金额根本无法凑出，那么它的 dp 值永远不会被更新，会一直等于初始值。所以最后只需要检查 dp[amount] 是否等于初始值即可。这里用dp[amount] != amount + 1判断，而不是dp[amount] == Integer.MAX_VALUE，就是为了避开大数加法的溢出风险。

5. 常见问题与排查技巧实录

5.1 返回结果判断：为什么 dp[amount] > amount 也能判断无解

我在前文提到 C++ 里用了dp[amount] > amount这个判断，有些读者可能会有疑问：为什么大于 amount 就代表无解？

因为 dp[i] 的初始值是 amount + 1，它本身就大于 amount。如果 dp[amount] 没有被更新过，它的值就是 amount + 1，确实大于 amount。但会不会出现 dp[amount] 被更新成了一个大于 amount 的合法值呢？不会。如果 amount 能被凑出来，最少硬币数一定不超过 amount（假设硬币面额最小为1时最多用 amount 枚；如果硬币最小面额大于1，那硬币数更少），所以合法的 dp[amount] 最大就是 amount，不可能大于 amount。

注意：这个逻辑成立的前提是硬币面额都是正整数。力扣这道题的约束条件正是如此。如果你在别的问题里遇到面额为0的硬币，这条判断就不适用了。

5.2 和"零钱兑换 II"的区别：最值问题 vs 计数问题

力扣 518 题"零钱兑换 II"长得和 322 几乎一模一样，但问的是"有多少种组合方式"，而不是"最少需要几枚硬币"。这是一个非常经典的对比场景。

322 的状态转移方程用的是min，因为我们在取最优值；518 用的是dp[i] += dp[i - coin]，因为我们在累加组合数。这两个动作的差异直接决定了题目类型：前者是"最值动态规划"，后者是"计数动态规划"。

更隐蔽的差异在于遍历顺序。518 要求组合数，外层循环必须遍历硬币，内层循环遍历金额，这样才能避免同一个组合因为硬币顺序不同被重复计数。322 求最值，硬币顺序不影响结果，所以外层循环遍历金额、内层循环遍历硬币也是正确的。我在面试中经常被问到这两题的区别，建议你把 518 也刷一遍，两题对比着理解。

5.3 另一个容易被问到的思路：把问题建模成 BFS

有些时候，面试官会换一个角度问这道题："你能不能不用动态规划，用其他方式解决？" 这时候 BFS 是一个不错的思路。

把金额想象成一个个节点，如果你当前在金额 i 这个节点，使用一枚面额 coin 的硬币，就能跳到节点 i - coin。从 amount 出发，目标是跳到 0。每"跳"一次，相当于使用了一枚硬币。所以这个问题就变成了一个在图中找最短路径的问题，BFS 天然适合。

def coinChangeBFS(coins, amount): from collections import deque queue = deque([amount]) visited = set([amount]) steps = 0 while queue: for _ in range(len(queue)): cur = queue.popleft() if cur == 0: return steps for coin in coins: nxt = cur - coin if nxt >= 0 and nxt not in visited: visited.add(nxt) queue.append(nxt) steps += 1 return -1

BFS 的复杂度在最坏情况下也是 O(amount × n)，但好处在于它天然适合"最少步数"的语义，而且避免了状态转移方程的抽象推导。不过 BFS 需要一个 visited 集合防止重复访问，空间占用比 dp 数组更大。两者没有绝对的优劣，面试时你可以先写 dp，再补充说"这题也能用 BFS 建模成最短路径问题"，这会让面试官觉得你的知识是成体系的。

5.4 我实际踩过的坑

刷这道题的过程中，我总结过几个真实的坑，写在这里给你提个醒。

第一个坑是把 dp 数组初始化为float('inf')而不是amount + 1。Python 里 float('inf') 在做加法时不会溢出，看起来好像没事，但问题在于：如果 dp[i - coin] 是 inf，那么 dp[i - coin] + 1 仍然是 inf，min 操作也能正常工作。可最后判断时，你得写dp[amount] == float('inf')，这在逻辑上没问题，但可读性稍差，而且如果用 C++ 或 Java，int 类型根本没有 inf 可用，会导致你写出容易溢出的代码。所以我在实际写代码时，统一使用 amount + 1 作为初始化值，让代码在所有语言里都能保持一致。

第二个坑是忘记处理 amount = 0。有的写法开头会有一行if amount == 0: return 0，这本身没问题，但如果你已经初始化 dp[0] = 0，这行其实是不必要的。多加一个判断不会错，但对面试来说，你要能说清楚这个判断有没有必要。

第三个坑是在内层循环里没有做coin <= i的判断。如果没有这个判断，当 coin 大于 i 时，dp[i - coin] 会访问一个负数下标，直接报错。这也是我前面为什么强调要对 coins 排序的原因：排序之后可以直接用 break 代替复杂的下标判断，代码更简洁。

6. 扩展与实战建议：如何把一道题的价值用到极致

6.1 通过一道题串联一类题

零钱兑换不是孤立的一道题，它属于"背包问题家族"中的完全背包问题。它的特征是硬币数量无限。与之形成对比的是 0-1 背包（每件物品只能用一次）。搞懂 322，你可以顺势挑战下面这几道题：

• 力扣 518：零钱兑换 II，计数版，感受 min 和累加的差异。
• 力扣 279：完全平方数，本质上是用完全平方数作为"硬币"去凑目标数的最小个数。
• 力扣 377：组合总和 IV，注意这题问的是排列数，遍历顺序和 518 正好相反。
• 力扣 198：打家劫舍，虽然看起来是数组问题，但同样是最值型的动态规划。

我个人刷题的习惯是：每做完一道题，就在笔记里写下"这道题的状态定义是什么、为什么这样定义、能不能迁移到其他题目"。322 的迁移能力特别强，因为你只要把 coins 换成平方数、步长、单词长度，题目立刻会变成另一道经典题。

6.2 面试现场怎么答这道题

面试时如果遇到这道题，我建议你在写代码之前，先口头说清楚三个关键点：

一是解释为什么不能用贪心。你不需要把反例背出来，只需要说"贪心追求的是当前最大面额，但局部最优不一定等于全局最优"，然后举一个最简单的反例即可。

二是说清楚状态定义。明确告诉面试官：dp[i] 表示凑成金额 i 需要的最少硬币数，dp[amount] 就是答案。

三是解释初始化。这也是加分项。你可以主动说"我特意把 dp 初始化成 amount + 1，而不是很大的数，是为了避免加法溢出，同时也能直接用这个值作为无解的标记"。这个细节在大多数人的答案里不会出现，但你一旦说出来，面试官就会知道你真正理解这道题，而不只是背了代码。

按照这三个步骤走下来，你基本可以在不用提示的情况下完成这道题。就算中途卡住，面试官提示的方向通常也是"你想一想子问题是什么"，而不是直接告诉你答案。

6.3 为什么我建议你用纸笔模拟一次

我前面手动推了一遍 dp 数组，这个动作看起来笨，但效果却出奇地好。原因在于：动态规划的状态转移方程通常只有一行，但这一行背后涉及"状态之间的依赖关系"，只看代码很难建立起直觉。

当你手动推完 11 个金额之后，你会自然而然地在心里形成一张表：金额越大，dp 值的变化规律是什么；哪个面额会经常被用到；无解的情况为什么不会被更新。这种直觉比背代码重要得多。

如果这张表一开始推不出来，我建议你从更小的例子开始，比如 amount = 6，coins = [1, 3, 4]，手动推一遍就会发现贪心失效的根源在哪里。把这个例子吃透之后，再回来推导前面那个大例子，你会觉得顺了很多。

这道题刷完，你得到的不仅仅是一个能 AC 的答案，更重要的是你彻底理解了"状态"和"转移"这两个动态规划的核心概念。希望这篇拆解对你有帮助，也希望你在面试中遇到这道题时，能从容地把思路讲清楚。