题目描述
硬币面额可重复使用，求凑出 amount 的组合数(顺序不算)。
coins = [1, 2, 5]
amount = 5
输出 = 4
思路解析
dp[0]=1，凑 0 块钱有一种方法：什么都不拿。外层枚举硬币，内层金额从小到大：dp[j] += dp[j−coin]。外层先遍历硬币，就能保证同一种组合不会重复算。
建表 · dp[0]=1：表头是金额 0 到 5。dp[0]=1（空组合），其他先设为 0。然后一枚一枚硬币累加。
用硬币 1：只有硬币 1 时，每个金额都只有一种凑法（全用 1）。所以 dp 全变成 1。
加入硬币 2：加入硬币 2，金额从小到大更新：dp[2]=2、dp[3]=2、dp[4]=3、dp[5]=3。从小到大保证了硬币 2 可以重复用。
加入硬币 5：最后加入硬币 5：dp[5] += dp[0] = 1，变成 4。这就是答案。
结论：dp[5] = 4，对应那 4 种组合，返回 4。
0-1 背包内层从大到小（每个物品只能用一次），完全背包内层从小到大（可以重复）。求组合数时外层套物品，求排列数时外层套容量。
参考代码（Python）
Python
1dp = [0] * (amount + 1); dp[0] = 1
2for coin in coins: # 外层：硬币
3 for j in range(coin, amount + 1): # 内层：金额从小到大
4 dp[j] += dp[j - coin]
5return dp[amount]复杂度分析
- 时间复杂度：O(n × amount) —— 硬币数 × 金额
- 空间复杂度：O(amount) —— 一维 dp
套路模板
记住骨架：完全背包内层从小到大。求组合数就外层物品内层容量；求排列数就把两层对调。
Python
1# 每个物品可无限次使用
2dp = [0]*(W+1); dp[0] = 1 # 计数：1；最值：0/inf
3for x in items: # 求组合数：外层物品
4 for j in range(x, W + 1): # 从小到大!
5 dp[j] += dp[j - x] # 或 min/max
6return dp[W]易错点
- ❌ 内层从大到小 → ✅ 完全背包内层从小到大（从大到小会变成每种硬币只用一次）
- ❌ 外层金额、内层硬币 → ✅ 求组合数要外层硬币（层序反了会把 1+2 和 2+1 当两种(排列)）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。