题目描述
思路解析
一句话答案：LeetCode 322 零钱兑换的标准解是完全背包式动态规划：dp[x] 表示凑出金额 x 的最少硬币数，枚举最后一枚硬币的面额 c，取 dp[x] = min(dp[x], dp[x-c] + 1)。面额不规则时贪心会漏最优，必须逐金额递推。时间 O(amount × k)（k 为面额种数）、空间 O(amount)，无解返回 -1。
零钱兑换在求什么
给定硬币面额数组 coins 和目标金额 amount，每种面额可以无限次使用，求凑出 amount 所需的最少硬币数；任何组合都凑不出时返回 -1。比如 coins = [1, 2, 5]、amount = 11，最优是 5 + 5 + 1，共 3 枚。要的是「最少枚数」这一个数字，不需要给出具体拿法。
为什么每次拿最大面额的贪心会错
生活直觉是找零先给大票子：能拿 5 就拿 5，剩下的再用小面额补。人民币这类面额体系下贪心恰好对，但对任意面额它会翻车——经典反例是 coins = [1, 3, 4] 凑 6，贪心先拿 4 再补两个 1 共 3 枚，最优却是 3 + 3 只要 2 枚。拿了最大面额后剩下的金额可能「很难凑」，局部省的在后面加倍还回来。
既然目光放在「第一枚拿什么」靠不住，就换到「最后一枚拿什么」上：凑出金额 x 的任何最优方案，其最后一枚硬币必是某个面额 c，去掉它之后剩下的部分一定是「凑出 x - c 的最优方案」——否则拿更优的替换进来，总枚数还能更少，与最优矛盾。这一步把大问题严格归约到小金额的同类问题，动态规划就此立住。
dp 下标为什么是金额而不是硬币位置
定义 dp[x] 为「恰好凑出金额 x 所需的最少硬币数」。下标用金额而不是硬币下标，是因为硬币可无限重复使用，「用到第几枚」不构成状态，真正决定后续走向的只有「还差多少钱」。起点 dp[0] = 0：凑出金额 0 一枚也不用，它是递推的地基。
其余位置先初始化为一个「不可能大」的哨兵值。参考代码用 amount + 1 而不是编程语言里的整数最大值，因为哨兵还要参与 + 1 运算，用最大值会溢出翻负；而任何合法答案至多 amount 枚（全用面额 1），所以 amount + 1 天然表示「暂时凑不出」。
转移方程为什么取 min 加一
从小到大算每个金额 x：枚举最后一枚硬币的面额 c，只要 x - c >= 0，就有一个候选方案「先用 dp[x-c] 枚凑出 x - c，再添一枚 c」，代价 dp[x-c] + 1。最后一枚硬币必然是某个面额，把每种面额的候选都看一遍取最小，就覆盖了凑出 x 的全部可能，dp[x] = min(dp[x], dp[x-c] + 1) 因此完整且正确。
顺序也有讲究：金额从 1 递增到 amount，保证算 dp[x] 时所有更小金额的答案已经就绪，引用的永远是定稿值。
复杂度怎么数，无解怎么判
外层金额 1 到 amount，内层枚举 k 种面额，每个格子 O(1)，总时间 O(amount × k)；一维数组 dp 长度 amount + 1，空间 O(amount)。
收尾判无解：若 dp[amount] 仍大于 amount，说明它从未被更新、还停在哨兵值，返回 -1。近亲题要分清：LeetCode 518 零钱兑换 II 求凑法总数，转移变成累加 dp[x] += dp[x-c]，且要把面额放在外层循环避免同一组合被重复计数——递推长得像，语义完全不同。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条转移式：枚举最后一枚硬币的面额，回看「剩下金额」要几枚，再 +1。下面每格都在套它。
上行是金额下标 0..11（固定不动），下行 dp 待填。dp[x] 表示凑出金额 x 最少要几枚硬币。从最左边开始。
凑出金额 0 不需要任何硬币：dp[0]=0。这是递推的地基。
算 dp[1]：枚举最后一枚硬币——用面额 1 → 看 dp[0]=0，再 +1 = 1。取这些候选里最小的。
最小是 1，填进 dp[1]。这一步选了面额 1（接在 dp[0]=0 后面再加一枚）。
算 dp[2]：枚举最后一枚硬币——用面额 1 → 看 dp[1]=1，再 +1 = 2；用面额 2 → 看 dp[0]=0，再 +1 = 1。取这些候选里最小的。
最小是 1，填进 dp[2]。这一步选了面额 2（接在 dp[0]=0 后面再加一枚）。
算 dp[3]：枚举最后一枚硬币——用面额 1 → 看 dp[2]=1，再 +1 = 2；用面额 2 → 看 dp[1]=1，再 +1 = 2。取这些候选里最小的。
最小是 2，填进 dp[3]。这一步选了面额 1（接在 dp[2]=1 后面再加一枚）。
算 dp[4]：枚举最后一枚硬币——用面额 1 → 看 dp[3]=2，再 +1 = 3；用面额 2 → 看 dp[2]=1，再 +1 = 2。取这些候选里最小的。
最小是 2，填进 dp[4]。这一步选了面额 2（接在 dp[2]=1 后面再加一枚）。
算 dp[5]：枚举最后一枚硬币——用面额 1 → 看 dp[4]=2，再 +1 = 3；用面额 2 → 看 dp[3]=2，再 +1 = 3；用面额 5 → 看 dp[0]=0，再 +1 = 1。取这些候选里最小的。
最小是 1，填进 dp[5]。这一步选了面额 5（接在 dp[0]=0 后面再加一枚）。
算 dp[6]：枚举最后一枚硬币——用面额 1 → 看 dp[5]=1，再 +1 = 2；用面额 2 → 看 dp[4]=2，再 +1 = 3；用面额 5 → 看 dp[1]=1，再 +1 = 2。取这些候选里最小的。
最小是 2，填进 dp[6]。这一步选了面额 1（接在 dp[5]=1 后面再加一枚）。
算 dp[7]：枚举最后一枚硬币——用面额 1 → 看 dp[6]=2，再 +1 = 3；用面额 2 → 看 dp[5]=1，再 +1 = 2；用面额 5 → 看 dp[2]=1，再 +1 = 2。取这些候选里最小的。
最小是 2，填进 dp[7]。这一步选了面额 2（接在 dp[5]=1 后面再加一枚）。
算 dp[8]：枚举最后一枚硬币——用面额 1 → 看 dp[7]=2，再 +1 = 3；用面额 2 → 看 dp[6]=2，再 +1 = 3；用面额 5 → 看 dp[3]=2，再 +1 = 3。取这些候选里最小的。
最小是 3，填进 dp[8]。这一步选了面额 1（接在 dp[7]=2 后面再加一枚）。
算 dp[9]：枚举最后一枚硬币——用面额 1 → 看 dp[8]=3，再 +1 = 4；用面额 2 → 看 dp[7]=2，再 +1 = 3；用面额 5 → 看 dp[4]=2，再 +1 = 3。取这些候选里最小的。
最小是 3，填进 dp[9]。这一步选了面额 2（接在 dp[7]=2 后面再加一枚）。
算 dp[10]：枚举最后一枚硬币——用面额 1 → 看 dp[9]=3，再 +1 = 4；用面额 2 → 看 dp[8]=3，再 +1 = 4；用面额 5 → 看 dp[5]=1，再 +1 = 2。取这些候选里最小的。
最小是 2，填进 dp[10]。这一步选了面额 5（接在 dp[5]=1 后面再加一枚）。
算 dp[11]：枚举最后一枚硬币——用面额 1 → 看 dp[10]=2，再 +1 = 3；用面额 2 → 看 dp[9]=3，再 +1 = 4；用面额 5 → 看 dp[6]=2，再 +1 = 3。取这些候选里最小的。
最小是 3，填进 dp[11]。这一步选了面额 1（接在 dp[10]=2 后面再加一枚）。
最右 dp[11]=3 就是凑出金额 11 的最少硬币数。若它是 ∞ 就返回 -1（本例是 3：5+5+1）。
边界先想清，尤其无解情形返回 -1。
两个高频追问——贪心反例 + 与 LC518 的区别。
参考代码
def coinChange(coins, amount): INF = amount + 1 dp = [0] + [INF] * amount for x in range(1, amount + 1): for c in coins: if x - c >= 0: dp[x] = min(dp[x], dp[x - c] + 1) return dp[amount] if dp[amount] <= amount else -1复杂度
- 时间：O(amount × k)，k=面额种数，每格枚举所有面额
- 空间：O(amount)，一维 dp 数组
易错点
面试追问把动画讲成自己的话
追问为什么不能用贪心？
追问本题求最少硬币数，若改求凑法总数呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
乘积最大子数组
LeetCode 152 · 中等 · 沿着 一维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题