LeetCode 322中等动态规划
零钱兑换 图解题解
这道题到底在问什么
给定硬币面额 coins=[1,3,4] 和金额 amount=6，求凑出 6 的最少硬币数；如果凑不出返回 -1。
- coins
- [1,3,4]
- amount
- 6
- 输出
- 2（3+3）
先想最直接的笨办法
最后一枚硬币枚举出来，状态转移就清楚了。（动画第 13 步）
最优解：一步一步想明白
- 3凑 11 会问凑 10、9、6；这些子金额又会重复出现。
- 4尝试每一枚硬币 c。如果 a-c 能凑出，就用它加一枚 c 更新 dp[a]。
- 5dp[0]=0，其余 ∞金额 0 不需要硬币，所以 dp[0]=0。其它金额先当作不可达，也就是无穷大。
- 6dp[1]=1当前格是金额 1，依赖格是金额 0。0 再加一枚 1 元硬币，就得到 1 枚。
- 7dp[2]=2没有 2 元硬币，只能从金额 1 再加一枚 1，得到两枚硬币。
- 8coin 3 直接胜出金额 3 有两个候选：从 2 加一枚 1，要 3 枚；从 0 加一枚 3，只要 1 枚。选最少。
- 9dp[4]=1金额 4 同时试硬币 1、3、4。只要看依赖格的值，就能知道直接用 4 最少。
- 10dp[6]=2这就是关键帧：贪心会先拿 4，剩 2 只能 1+1，共 3 枚；DP 同时看所有候选，发现 3+3 只要 2 枚。
- 13最后一枚硬币枚举出来，状态转移就清楚了。
- 16not greedycoins=[1,3,4], amount=6。贪心先拿 4，会得到 4+1+1 三枚；DP 找到 3+3 两枚。
- 23这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：INF 设太大可能溢出
✓ 对：用 amount+1
最差也不会超过 amount 枚 1 元硬币。
✗ 错：忘记 dp[0]=0
✓ 对：金额 0 是所有转移的地基
直接用一枚硬币凑成 c 依赖 dp[0]+1。
✗ 错：把不能凑的 ∞ 当答案返回
✓ 对：最后转成 -1
题目要求不能凑成返回 -1。
完整代码（Python / C++ / Java）
Python
class Solution:
def coinChange(self, coins, amount):
INF = amount + 1
dp = [INF] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if a >= c:
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == INF else dp[amount]C++
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int INF = amount + 1;
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (a >= c) dp[a] = min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
};Java
class Solution {
public int coinChange(int[] coins, int amount) {
int INF = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (a >= c) dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
}套路模板 · 零钱兑换迁移骨架
# 1. 说清 dp[状态] 的含义
dp = 初始值
for state in 遍历顺序:
for choice in 可选动作:
candidate = dp[前置状态] + 这次选择的代价
dp[state] = best(dp[state], candidate)
return dp[答案状态]// 1. 先定义 dp[state] 的含义
vector<int> dp(状态数, 初始值);
for (auto state : 遍历顺序) {
for (auto choice : 可选动作) {
auto candidate = dp[前置状态] + 代价;
dp[state] = best(dp[state], candidate);
}
}
return dp[答案状态];// 1. 先定义 dp[state] 的含义
int[] dp = new int[状态数];
Arrays.fill(dp, 初始值);
for (State state : 遍历顺序) {
for (Choice choice : 可选动作) {
int candidate = dp[前置状态] + 代价;
dp[state] = best(dp[state], candidate);
}
}
return dp[答案状态];复杂度
时间复杂度
O(amount · m)
每个金额尝试 m 种硬币
空间复杂度
O(amount)
dp 数组长度 amount+1
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 零钱兑换 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么不能贪心？+
一般硬币系统不满足贪心性质，像 [1,3,4] 凑 6 就会失败。
这道题为什么用「动态规划」，换最直接的暴力解会差在哪？+
动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。