题目描述
硬币面额 coins（每种可无限用），凑出金额 amount，最少需要几枚？凑不出返回 -1。
思路解析
咱们建一行表格，dp[j] 记录「凑出金额 j 最少要几枚」。从金额 0 开始，一格一格往右推，大金额会用到前面小金额的答案。
凑金额 j，最后那一枚硬币如果是面额 c，那剩下的就是「凑 j−c」的问题（已经算过了），再 +1 枚。把每种硬币都试一遍，取最少的：dp[j] = min(dp[j−c] + 1)。
建表 · 边界：凑金额 0 不需要硬币，dp[0] = 0。其它先记成 ∞（无穷大，表示「还不知道 / 暂时凑不出」）。
金额 1：凑 1：只能用一枚面额 1。= dp[0] + 1 = 1 枚。（面额 2、5 比 1 大，用不了）
金额 2 · 试面额1：凑 2，先试面额 1：剩下凑 1（dp[1]=1）再加这枚 = 2 枚。先记着这个候选。
金额 2 · 试面额2：再试面额 2：剩下凑 0（dp[0]=0）加一枚 = 1 枚。比刚才的 2 更少！所以 dp[2] = 1。
金额 3：凑 3：用面额1 → dp[2]+1=2；用面额2 → dp[1]+1=2。都是 2，dp[3] = 2。（面额5 太大跳过）
金额 4：凑 4：用面额1 → dp[3]+1=3；用面额2 → dp[2]+1=2。取小，dp[4] = 2（两枚 2）。
金额 5 · 试1和2：凑 5：用面额1 → dp[4]+1=3；用面额2 → dp[3]+1=3。先记候选 3。但别忘了还有面额 5！
金额 5 · 试面额5：试面额 5：剩下凑 0 加一枚 = 1 枚！比 3 少多了。dp[5] = 1（就一枚 5）。
金额 6 · 试面额1：终于到金额 6。先试面额 1：dp[5]+1 = 1+1 = 2 枚。记着候选 2。
金额 6 · 试面额2：再试面额 2：dp[4]+1 = 2+1 = 3 枚。比已有候选 2 还多，不采用。
金额 6 · 试面额5：最后试面额 5：dp[1]+1 = 1+1 = 2 枚（5 + 1）。和候选 2 一样。所有硬币试完，dp[6] = 2。
答案：表格最后一格 dp[6] = 2 就是答案：凑出 6 最少 2 枚（5 + 1）。
把大问题拆成「减掉一枚硬币后的小问题」，是 DP 的典型思路。零钱兑换 II、完全平方数、组合总和 IV 都是同款。
参考代码（Python）
1def coinChange(self, coins, amount):
2 dp = [amount + 1] * (amount + 1) # amount+1 当作class="cl-str">"∞"(枚数不可能超过 amount)
3 dp[0] = 0 # 凑 0 元要 0 枚
4 for j in range(1, amount + 1): # 金额从小到大
5 for c in coins: # 试每种硬币
6 if c <= j:
7 dp[j] = min(dp[j], dp[j-c] + 1) # 取最少
8 return dp[amount] if dp[amount] <= amount else -1复杂度分析
- 时间复杂度：O(amount × 种类) —— 每个金额试每种硬币
- 空间复杂度：O(amount) —— 一行 dp 数组
套路模板
求最少/方案数的「凑数」题都套它：外层金额、内层选项，dp[j] 从更小的 dp[j-c] 推来。
1dp = [INF]*(amount+1)
2dp[0] = 0
3for j in range(1, amount+1):
4 for c in coins:
5 if c <= j:
6 dp[j] = min(dp[j], dp[j-c] + 1)
7return dp[amount] if dp[amount] != INF else -1易错点
- ❌ dp 初值设成 0 → ✅ 初值设成 INF（凑不出），只有 dp[0]=0（求最小值，初值必须够大才不会被错误选中）
- ❌ 凑不出时不处理 → ✅ 最后判断 dp[amount] 是否仍是 INF → 返回 -1（有些金额本就凑不出来）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。