零钱兑换 II：组合数要把硬币放外层
问有多少种凑法，顺序不同算同一种。外层按硬币、内层金额正序 dp[j]+=dp[j−c]，每种组合只按硬币出现顺序记一次。
dp[0]=1。对每枚硬币 c，正序扫 j=c..amount：dp[j]+=dp[j−c]。硬币在外层，组合按固定硬币顺序生成，1+2 与 2+1 不会重复。答案 dp[amount]。时间 O(A·C)，空间 O(A)。
这是 LeetCode 518. Coin Change II。给你不同面额的硬币 coins 和总金额 amount，每种硬币无限枚，问凑出 amount 有多少种组合。顺序不同算同一种：1+2 和 2+1 是一种，不是两种。
主例 coins = [1, 2, 5]，amount = 5。四种凑法：五个 1；一个 2 加三个 1；两个 2 加一个 1；一个 5。答案是 4。
LC322 问最少用几枚，那是另一张表。这里若把金额放外层、硬币放内层，会把 1+2 和 2+1 都加上，得到排列数。缺的是「先定硬币种类、再累金额」这条顺序。下面从这块缺口推出外层硬币的完全背包。
外层硬币，才是组合
输入给的是面额列表和目标金额。每种面额可以用 0 次、1 次、多次。方案是多重集合，不是序列。所以状态不该记住「最后一枚是谁的顺序」，只该记住「用到现在这些面额，凑出 j 有几种」。
第一直觉是对每个金额 j 枚举最后一枚硬币。dp[j] 加上 dp[j−c]，每个 j 都能用到全部面额。这样 5 可以先 1 再 2 再 2，也可以先 2 再 1 再 2，路径不同就被加了多次。缺的是一个强制顺序：先考虑完硬币 1 的所有用法，再引入硬币 2，再引入 5。同一种集合只会在这个固定顺序下出现一次。
从缺口反推。一维数组 dp[j] 表示「只用到目前已引入的硬币，凑出 j 的组合数」。dp[0]=1，什么都不选是一种。引入硬币 c 时，j 从 c 正序走到 amount：dp[j]+=dp[j−c]。正序才能在同一轮里用到刚刚更新过的 dp[j−c]，也就是同一枚硬币用多次——完全背包。倒序会变成 0-1，每种面额最多一枚，主例会丢掉 2+2+1。
用手走主例。先引入 1。j=1..5 每次加 dp[j−1]，全变成 1：每个金额只有「全用 1」一种。演示第一帧 dp=[1,1,1,1,1,1]，cur 指向硬币 1。再引入 2。j=2：1+dp[0]=2；j=3：1+dp[1]=2；j=4：1+dp[2]=3；j=5：1+dp[3]=3。表变成 [1,1,2,2,3,3]。dp[5]=3 对应 1×5、2+1×3、2+2+1，还没有 5。最后引入 5。只有 j=5：3+dp[0]=4。演示第三帧 dp[5]=4，四种凑法齐了。
金额放外层会得到 LC377 那种排列数，主例会大于 4，不要背「双重循环」却记反层次。amount=0 时只有空组合，返回 1。没有硬币且 amount>0，dp 停在 0。每个 (硬币, 金额) 对更新一次，时间 O(A·C)，只要一维数组。
循环层次就是组合与排列硬币在外：每种集合按硬币顺序生成一次，是组合。金额在外：同一集合可按不同最后一枚到达，是排列。主例必须是前者，答案才是 4。
Go：完全背包组合数
func change(amount int, coins []int) int {dp := make([]int, amount+1)dp[0] = 1for _, c := range coins {for j := c; j <= amount; j++ {dp[j] += dp[j-c]}}return dp[amount]}
1dp[0]=1 是空组合。amount 为 0 时直接返回这个 1。
2外层 range coins：先用完一种面额，再引入下一种，组合不会按不同顺序重复。
3内层 j 从 c 正序走：同一枚 c 可以连用，这是完全背包。倒序会错成 0-1。
4主例三轮之后 dp[5]=4，就是那四种凑法。
总结
组合数：硬币在外、金额正序累加。主例引入 1、2、5 之后 dp[5]=4。
- LC322 问最少枚数；本题问方案数。把循环对调会变成排列，主例不再是 4。
- 正序才能复用当前硬币。2+2+1 依赖同一轮里更新过的 dp[3]。
- dp[0]=1 不能省。没有它，加 dp[j−c] 全是 0。