硬币找零方案数
动态规划 · 计数
不求最优，只数方案
前几页 DP 求的都是「最优值」——最少代价、最大价值。还有一大类 DP 求的是方案数：给若干面额的硬币、每种无限枚，问凑出目标金额有多少种不同组合。这就是计数 DP。
把「取 max」换成「相加」
设 dp[i][a] = 只用前 i 种硬币凑出金额 a 的方案数。它和 完全背包长得几乎一样——同样是「无限次取」的二维表，「用一枚」的来源也在本行dp[i][a-面额]。差别只在算子：
完全背包在「不取」和「取」之间取 max；硬币找零则把两条路的方案数相加——dp[i][a] = dp[i-1][a]（不用这种硬币的方案数） + dp[i][a-面额]（至少用一枚这种硬币的方案数）。边界也不同：dp[0][0] = 1——凑出 0 元有 1 种方案（什么都不选），这个「1」是所有方案数的种子。
下面固定硬币 [1, 2, 5]、金额 5。点「下一步」逐格看：当前格琥珀环，「不用」的上一行格和「用一枚」的本行左侧格都黄色高亮，两个方案数相加填入即变绿。走到底，右下角 = 4（四种凑法：1×5、1×3+2、1+2×2、5）。右侧代码随每一步同步高亮。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| ∅ | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | ||||||
| 2 | ||||||
| 5 |
边界：凑出金额 0 只有 1 种方案（什么硬币都不选）→ dp[0][0]=1；第 0 行其余金额都凑不出，为 0
1function change(amount: number, coins: number[]): number {
2 const m = coins.length;
3 const dp = Array.from({ length: m + 1 },
4 () => Array(amount + 1).fill(0));
5 dp[0][0] = 1; // 凑 0 元有 1 种：什么都不选
6 for (let i = 1; i <= m; i++) {
7 const c = coins[i - 1];
8 for (let a = 0; a <= amount; a++) {
9 dp[i][a] = dp[i - 1][a]; // 不用第 i 种硬币
10 if (a >= c) dp[i][a] += dp[i][a - c]; // 用一枚（本行，可再用）
11 }
12 }
13 return dp[m][amount];
14}
硬币1,2,5
金额5
1 / 20
计数 DP 在哪里用
组合计数：找零方案、爬楼梯方法数、路径条数、可达状态数。
概率 / 期望：把「方案数」换成「概率累加」，同一套递推。
对照最优 DP：把递推里的 max/min 换成加法、边界 1 而非 0——同一张表，问的问题不同。
概率 / 期望：把「方案数」换成「概率累加」，同一套递推。
对照最优 DP：把递推里的 max/min 换成加法、边界 1 而非 0——同一张表，问的问题不同。
建议和 完全背包对照着看：同样一张「无限次取」的二维表、同样的本行来源，只把「取 max」改成「方案数相加」，求的就从最大价值变成了组合总数。