Dynamic Programming

Coin Denominations

1

3

4

= 8

target

dp[i] = minimum coins to make amount i

0

∞

∞

∞

∞

∞

∞

∞

∞

Press Play to begin filling the DP table.

Debugger · v1.0

LIVE

1function coinChange(coins, amount) {

2 // 1: dp[i] = min coins to make i

3 const dp = Array(amount+1).fill(Infinity);

4 dp[0] = 0;

6 // 4: Fill each amount 1..amount

7 for (let i = 1; i <= amount; i++) {

8 // 5: Try every coin

9 for (const coin of coins) {

10 if (i < coin) continue;

11 // 6: Compute candidate

12 const candidate = dp[i - coin] + 1;

13 // 7: Keep the minimum

14 dp[i] = Math.min(dp[i], candidate);

15 }

16 }

18 // 9: Impossible if still Infinity

19 if (dp[amount] === Infinity) return -1;

21 // 11: Backtrack to find coins used

22 // 12: Return minimum coin count

23 return dp[amount];

24}

Debugger · v1.0

LIVE

1function coinChange(coins, amount) {

2 // 1: dp[i] = min coins to make i

3 const dp = Array(amount+1).fill(Infinity);

4 dp[0] = 0;

6 // 4: Fill each amount 1..amount

7 for (let i = 1; i <= amount; i++) {

8 // 5: Try every coin

9 for (const coin of coins) {

10 if (i < coin) continue;

11 // 6: Compute candidate

12 const candidate = dp[i - coin] + 1;

13 // 7: Keep the minimum

14 dp[i] = Math.min(dp[i], candidate);

15 }

16 }

18 // 9: Impossible if still Infinity

19 if (dp[amount] === Infinity) return -1;

21 // 11: Backtrack to find coins used

22 // 12: Return minimum coin count

23 return dp[amount];

24}

State Inspector

No variables in scope.

Amount:8

412

Dynamic Programming

Coin Change (Min Coins)

Step 1 of 6

Given coin denominations and a target amount, find the minimum number of coins needed. A classic DP problem that shows why greedy fails — and how bottom-up tabulation always finds the optimal answer.

Why Greedy Fails

Greedy always picks the largest coin first. With coins [1, 3, 4] and target 6: greedy picks 4+1+1 = 3 coins. DP finds 3+3 = 2 coins. The optimal substructure of this problem requires DP, not greedy.

Greedy

4

1

1

3 coins ✕

3

3

2 coins ✓