零钱兑换 II

最直接的想法：递归枚举「面额 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 背包内层从大到小（每个只用一次）。求组合数外层套物品、内层套容量；求排列数把两层对调。这一句记牢，一类题全通。

边界三连：三种边界先想清。

面试官常追问：四个高频追问，组合/排列别搞混。