Coin Change
The key insight: the minimum coins for amount i only depends on the minimum coins for smaller amounts you've already solved — pick a coin, and the rest of the amount (i - coin) is just a smaller subproblem you can look up. Build a table bottom-up from dp[0] = 0, and for every amount try every coin as the 'last coin used', keeping whichever choice leaves the fewest coins behind. dp[i] holds that running best, so dp[amount] is the answer once every smaller amount has already been solved.
Details
Animated on: coins=[1,2,5], amount=6, find minimum number of coins
Problem:Coin ChangeMedium
Pattern:1D Dynamic Programming
Dynamic Programming
step 1 / 8
Initialize dp[0] = 0, base case: 0 coins needed for amount 0
1FUNCTION coinChange(coins, amount):2 dp = a table of size amount + 1, all set to Infinity3 dp[0] = 04 FOR i from 1 to amount:5 FOR each coin in coins:6 IF coin <= i:7 dp[i] = the smaller of dp[i] and dp[i-coin] + 18 RETURN dp[amount]
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Initialize dp[0] = 0, base case: 0 coins needed for amount 0
- dp[1] = dp[0] + 1 = 0 + 1 = 1, using coin 1 (smallest denomination)
- dp[2] = min(dp[1] + 1 = 2, dp[0] + 1 = 1) = 1, using coin 2
- dp[3] = min(dp[2] + 1 = 2, dp[1] + 1 = 2) = 2, using coin 1
- dp[4] = min(dp[3] + 1 = 3, dp[2] + 1 = 2) = 2, using coin 2
- dp[5] = min(dp[4] + 1 = 3, dp[3] + 1 = 3, dp[0] + 1 = 1) = 1, using coin 5
- dp[6] = min(dp[5] + 1 = 2, dp[4] + 1 = 3, dp[1] + 1 = 2) = 2, minimum coins for amount 6
- Answer: dp[6] = 2 minimum coins (5+1 = 6 uses 2 coins; 2+2+2 = 6 also uses 3 coins, minimum is 2)
Now solve it yourself
Watching is the first half. The second is writing it without the animation.