题目描述
思路解析动画文字版
凑 11 会问凑 10、9、6；这些子金额又会重复出现。
尝试每一枚硬币 c。如果 a-c 能凑出，就用它加一枚 c 更新 dp[a]。
初始化 · 只有 0 可达：金额 0 不需要硬币，所以 dp[0]=0。其它金额先当作不可达，也就是无穷大。
金额 1 · 只能从 0 加硬币 1：当前格是金额 1，依赖格是金额 0。0 再加一枚 1 元硬币，就得到 1 枚。
金额 2 · 只能 1+1：没有 2 元硬币，只能从金额 1 再加一枚 1，得到两枚硬币。
金额 3 · 候选里选最少：金额 3 有两个候选：从 2 加一枚 1，要 3 枚；从 0 加一枚 3，只要 1 枚。选最少。
金额 4 · 4 元硬币直接凑成：金额 4 同时试硬币 1、3、4。只要看依赖格的值，就能知道直接用 4 最少。
金额 6 · 贪心翻车，DP 胜出：这就是关键帧：贪心会先拿 4，剩 2 只能 1+1，共 3 枚；DP 同时看所有候选，发现 3+3 只要 2 枚。
最后一枚硬币枚举出来，状态转移就清楚了。
边界三连：金额 0、不可达、非贪心最优，都要在 DP 里显式跑过。
雷区实演 · 贪心会错：coins=[1,3,4], amount=6。贪心先拿 4，会得到 4+1+1 三枚；DP 找到 3+3 两枚。
面试追问 1：一般硬币系统不满足贪心性质，像 [1,3,4] 凑 6 就会失败。
面试追问 2：每种硬币可用无限次，金额维度上的转移就是完全背包。
面试追问 3：求最少硬币时金额外层、硬币内层最直观；硬币外层也可做完全背包，但要理解含义。
这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
参考代码
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]复杂度
- 时间复杂度：O(amount · m)，每个金额尝试 m 种硬币
- 空间复杂度：O(amount)，dp 数组长度 amount+1
可套用的代码模板
这一步不是复读 零钱兑换 的参考答案，而是抽出这题真正能迁移的骨架；换题时先判断状态/容器含义，再填核心分支。
# 1. 说清 dp[状态] 的含义dp = 初始值for state in 遍历顺序: for choice in 可选动作: candidate = dp[前置状态] + 这次选择的代价 dp[state] = best(dp[state], candidate)return dp[答案状态]易错点
面试追问把动画讲成自己的话
追问这题为什么不能贪心？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
乘积最大子数组
LeetCode 152 · 中等 · 沿着 一维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题