题目描述
硬币面额可重复使用，求凑出 amount 的组合数（顺序不算，1+2 和 2+1 算同一种）。
思路解析
最直接的想法：递归枚举「面额 1 用几枚、面额 2 用几枚、面额 5 用几枚」，凑够 5 就记一种。可这样不同硬币的搭配会指数爆炸，而且「凑剩下 3 块有几种」这种子问题会被反复重算，慢得离谱。
转折：把「凑 j 有几种」记进 dp[j]，重叠子问题就只算一次。状态：dp[j]=凑出 j 的组合数；转移：加入面额 coin 后 dp[j] += dp[j−coin]（凑 j 的新法 = 先凑好 j−coin 再添一枚 coin）。外层枚举硬币、内层金额从小到大，就保证同一种组合只按「硬币种类顺序」数一次，不会把 2+1 和 1+2 当两种。
建表 · dp[0]=1：表头是金额 0 到 5，一行 6 格，全程不变。dp[0]=1：凑 0 块有一种办法，就是什么都不拿（空组合）。其余先记 0，还没开始放硬币。
硬币1 · 全程能加：先放面额 1。从 j=1 到 5 依次 dp[j] += dp[j−1]：dp[1]=dp[0]=1、dp[2]=dp[1]=1…一路全是 1。意思是只用 1时每个金额都只有「全用 1」这一种凑法。
加入硬币2 · 填 dp[2]：换面额 2，内层金额仍从小到大。先填 dp[2]：在原来「1+1」之外，多了一种「直接一枚 2」，来源是 dp[2−2]=dp[0]=1。所以 dp[2] = 1 + 1 = 2。
硬币2 · 填 dp[3]：dp[3]：加一枚 2 后剩 1，dp[1]=1（即 2+1）。dp[3] = 原来的 1（1+1+1）+ 1 = 2。
硬币2 · 填 dp[4]：dp[4] 用到刚更新过的 dp[2]=2——这正是从小到大的妙处：面额 2 可以重复用。dp[4] = 1 + 2 = 3（对应 1+1+1+1、2+1+1、2+2）。
硬币2 · 填 dp[5]：面额 2 收尾，dp[5] += dp[3]=2，从 1 涨到 3。现在只用 1 和 2，凑 5 已经有 3 种。还差面额 5 没放。
加入硬币5 · dp[1..4] 不变：换面额 5。内层金额从 coin=5 起步，所以金额 小于 5 的格子这一轮碰都不碰（不可能用上一枚 5），dp[1] 到 dp[4] 保持不变。只剩 dp[5] 要更新。
硬币5 · 填 dp[5]：dp[5] += dp[5−5]=dp[0]=1：多出来的这一种就是单独一枚 5。dp[5] 从 3 变成 4。三种硬币全放完了。
答案：表格最后一格 dp[5] = 4 就是答案，对应那 4 种组合：5、2+2+1、2+1+1+1、1×5。返回 4。
完全背包内层从小到大（硬币可重复），0-1 背包内层从大到小（每个只用一次）。求组合数外层套物品、内层套容量；求排列数把两层对调。这一句记牢，一类题全通。
参考代码（Python）
1def change(self, amount, coins):
2 dp = [0] * (amount + 1)
3 dp[0] = 1 # 凑 0 块：空组合，1 种
4 for coin in coins: # 外层：枚举硬币（保证组合不重复）
5 for j in range(coin, amount + 1): # 内层：金额从小到大
6 dp[j] += dp[j - coin] # 凑 j 多了「先凑 j−coin 再添一枚 coin」
7 return dp[amount]复杂度分析
- 时间复杂度：O(n × amount) —— n 种硬币各扫一遍金额，每格做一次加法
- 空间复杂度：O(amount) —— 只用一行长度 amount+1 的 dp 数组
套路模板
记住骨架：外层物品、内层容量从小到大、dp[j] += dp[j−x]。求排列数就把两层循环对调，求最少枚数就把 += 换成 min(dp[j], dp[j−x]+1)。
1# 每个物品可无限次使用，求凑出 W 的组合数
2dp = [0] * (W + 1)
3dp[0] = 1 # 计数初值 1（最值题改 0 或 INF）
4for x in items: # 求组合数：外层物品
5 for j in range(x, W + 1): # 完全背包：内层从小到大
6 dp[j] += dp[j - x] # 计数用 +=；最值用 min/max
7return dp[W]易错点
- 错误写法：for j in range(coin, amount+1) 写成内层硬币、外层金额 → 正确写法：求组合数必须外层枚举硬币、内层枚举金额（层序反了会把 1+2 和 2+1 当成两种，数出来的是排列数（LC377）不是组合数）
- 错误写法：for j in range(amount, coin-1, -1) 内层从大到小 → 正确写法：完全背包内层从小到大（从大到小会让每种硬币只能用一次，退化成 0-1 背包，凑 5 只剩 2 种）
- 错误写法：dp[0] 忘了置 1，整张表全 0 → 正确写法：dp[0]=1 是递推的种子（dp[0] 是「凑 0 块的空组合」，是所有 dp[j] += dp[j−coin] 的起点，漏了答案恒为 0）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。