Coin Change

Coin change is a classic DP problem that comes in two flavors: finding the fewest coins to make an amount, and counting the number of distinct ways to make it. The first is an unbounded knapsack; the second changes only the aggregation from min to sum.

Why Greedy Fails

A greedy strategy always picks the largest coin that fits. For US coins (25, 10, 5, 1) it works. But with coins 4 and target 6:

• Greedy: 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

Any coin set where a denomination skips a natural multiple can break greedy. DP considers every combination exhaustively.

Fewest Coins

State: dp[amount] = minimum coins needed to make exactly amount.

Recurrence: dp[a] = min over all coins c where c <= a of (dp[a - c] + 1)

Base cases: dp[0] = 0; all other values start at Infinity.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 6, 9], 11)); // 2 — (5+6)
console.log(coinChange([2], 3));            // -1 — impossible

Time O(amount * coins.length), space O(amount).

Count Ways

State: dp[amount] = number of distinct coin combinations summing to amount.

Recurrence: dp[a] += dp[a - coin] for each coin where coin <= a.

Base case: dp[0] = 1 (one way to make 0: use no coins).

The loop order matters: iterate coins in the outer loop and amounts in the inner loop. This treats different orderings of the same coins as the same combination (e.g., 1+2 and 2+1 both count once).

function countWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;

  // Outer loop over coins ensures each combination is counted once
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }
  return dp[amount];
}

console.log(countWays([1, 2, 5], 5));
// 4 — (5), (2+2+1), (2+1+1+1), (1+1+1+1+1)

If you swap the loop order (amount outer, coins inner), each permutation is counted separately — that answers the distinct-sequences variant.

Comparison

Greedy Coin Systems

Greedy works when the coin system is canonical — every denomination divides evenly into the next larger one, or the system satisfies the greedy property for all amounts. Standard currency systems (US, Euro) are designed this way. For arbitrary inputs, always use DP.

Up Next

Now that you have covered the core DP patterns, the next section introduces greedy algorithms — a faster family of techniques for the subset of problems where the greedy-choice property holds.