Coin Change II — Step-by-Step Visualization

Algorithm Pattern

2-D DP (Bottom-Up)

Key Idea

dp[i][a] = number of ways to make amount a using only coins[i:]. Each cell either skips the current coin (take from row below) or uses it (take from same row, a−coin columns back).

Step-by-Step Approach

1. Build a (n+1) × (amount+1) grid. Row i = decisions for coins[i:], column a = target amount.
2. Base row (i = n, no coins left): dp[n][0] = 1, all others = 0. Only way to make 0 with nothing is 'take nothing'.
3. Fill bottom-up (i = n−1 → 0). For each cell dp[i][a]:
4. Skip coin i: dp[i][a] += dp[i+1][a] (inherit from row below)
5. Use coin i: dp[i][a] += dp[i][a−coins[i]] (if a ≥ coins[i], same row!)
6. Answer is dp[0][amount] — using all coins to make the full amount.

Common Gotchas

• 'Use coin' pulls from the SAME row dp[i][...], not dp[i+1][...]. That's what allows unlimited use.
• Column 0 is always 1 for every row — there's exactly one way to make amount 0: use no coins.