Coin Change

How it works, step by step

1. 1

   Build a table: one column per amount from 0 to the target, one row per coin type you allow.

2. 2

   The first cell is free: amount 0 needs 0 coins. Every other cell builds on it.

3. 3

   Each cell asks two questions. Skip the row's newest coin: copy the answer from the row above. Take it once: look left by the coin's value in the same row, and add 1.

4. 4

   Keep the smaller of the two. That cell is now the proven best for its amount and its coin set - no guess involved.

5. 5

   Fill left to right, row by row. The bottom-right cell is the fewest coins for the full target.

6. 6

   To learn which coins were used, walk backwards from the answer: if the cell equals the one above, the coin was skipped; otherwise take the coin and jump left by its value.

The code, in JavaScript

function minCoins(coins, amount) {
  // dp[a] = fewest coins that make amount a.
  // Infinity = "cannot be made yet" - NOT 0!
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;                        // amount 0: take nothing

  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      // Best without this coin (dp[a]) vs
      // take one coin + best for what remains (dp[a - coin] + 1).
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

minCoins([1, 3, 4], 10);   // → 3   (4 + 3 + 3)
minCoins([25, 10, 5, 1], 30); // → 2  (25 + 5)
minCoins([2, 5], 3);       // → -1  (3 cannot be made)

Dry run: making 10 with coins {1, 3, 4}

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Greedy really is correct for US coins - and that success is the trap. Swap in {1, 3, 4} and greedy pays 4 coins for amount 10 when 3 is enough. No exception, no warning, just a wrong number in production.
• Initialize dp with Infinity, not 0. Zeros make every amount look already solved, so `Math.min` never updates anything. Only dp[0] starts at 0. Bonus: in JavaScript `Infinity + 1` is still `Infinity`, so unreachable amounts stay unreachable through the math.
• dp[amount] can still be Infinity at the end ({2, 5} can never make 3). Return -1 or null explicitly - otherwise Infinity leaks into the caller's arithmetic.
• Counting the number of ways to make change looks like a one-line edit (`+=` instead of `Math.min`) - but suddenly loop order matters. Coins outside, amounts inside counts each combination once. Amounts outside counts orderings too, so 1+3 and 3+1 both count. For fewest coins either order works, which is exactly why the trap goes unnoticed.

Coin Change vs. its closest relatives