Coin Change II
The insight: this counts COMBINATIONS, not permutations — [1,2,2] and [2,1,2] should count as the same way to make 5, not two different ways. Looping coins in the OUTER loop and amounts in the INNER loop enforces that: by fully processing one coin denomination before ever touching the next, a combination can only be built by adding coins in a fixed relative order, so the same multiset of coins can never be counted twice via two different orderings. dp[a] accumulates the running count of ways to make amount a using only the coin denominations introduced so far.
Details
Animated on: amount=5, coins=[1,2,5], count combinations (order doesn't matter)
Problem:Coin Change IIMedium
Dynamic Programming
step 1 / 5
Initialize dp[0]=1, dp[1..5]=0, way to make sum 0: 1 empty combination
1FUNCTION coinChange2(amount, coins):2 dp = a table of size amount + 1, all set to 03 dp[0] = 14 FOR each coin in coins:5 FOR a from coin to amount:6 add dp[a-coin] to dp[a]7 RETURN dp[amount]
← / → step · space play · Home restart
Every step in words
Show all 5 steps
- Initialize dp[0]=1, dp[1..5]=0, way to make sum 0: 1 empty combination
- Process coin=1 fully (inner loop left to right): dp[1..5] all become 1 using only 1-denomination combinations
- Process coin=2: dp[2]+=dp[0]=1→2, dp[3]+=dp[1]=1→2, dp[4]+=dp[2]=2→3, dp[5]+=dp[3]=2→3
- Process coin=5: dp[5]+=dp[0]=3+1=4, final dp[5]=4 combinations for amount 5
- Answer: dp[5]=4 — the 4 combinations are 5; 2+2+1; 2+1+1+1; 1+1+1+1+1 (order doesn't matter, so 1+2+2 isn't counted separately from 2+2+1).
Now solve it yourself
Watching is the first half. The second is writing it without the animation.