ENDEAR
Start free
algorithmpro

Dynamic programming: coin change

Find the fewest coins that make an amount, a problem where grabbing the biggest coin first fails.

time
O(n·m)
space
O(n)

// step through it

step 1 / 15
1function coinChange(coins, amount) {2  const dp = new Array(amount + 1).fill(Infinity);3  dp[0] = 0;4  for (let a = 1; a <= amount; a++) {5    for (const c of coins) {6      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;7    }8  }9  return dp[amount] === Infinity ? -1 : dp[amount];10}
coins
= [1, 3, 4]
  1. 00
  2. ∞1
  3. ∞2
  4. ∞3
  5. ∞4
  6. ∞5
  7. ∞6

dp[0] = 0: zero coins make 0. Every other amount starts at ∞, meaning not reachable yet.

// pro lesson

Unlock the full walkthrough

This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.

See pricing

How it works

With coins 1, 3 and 4, greedy picks 4 + 1 + 1 for 6, but 3 + 3 needs only two coins. Dynamic programming tries every option without repeating work: dp[a] is the fewest coins for amount a, and for each coin c, dp[a − c] + 1 is a candidate. Fill dp from 0 up to the amount. O(n·m) time for amount n and m coins, and O(n) space.

Practice spotting this pattern →