Pattern visualizer
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. Animated on: coins=[1,2,5], amount=6, find minimum number of coins.
Dynamic Programming
time O(n * amount)space O(amount)step 1 / 8
0
[0]--
[1]--
[2]--
[3]--
[4]--
[5]--
[6]line 3
Initialize dp[0] = 0, base case: 0 coins needed for amount 0
Pseudocode
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