Coin Change

The problem

Given coin denominations coins (unlimited supply of each) and an amount, return the fewest coins needed to make exactly that amount, or -1 if it can't be made.

Example: coins = [1, 2, 5], amount = 11 → answer 3 (5 + 5 + 1).

Approach 1 — Greedy (and why it's wrong)

"Always take the biggest coin that fits" feels right and works for standard currencies:

// WRONG in general
function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a)
  let count = 0
  for (const coin of coins) {
    count += Math.floor(amount / coin)
    amount %= coin
  }
  return amount === 0 ? count : -1
}

But take coins = [1, 3, 4], amount = 6: greedy grabs 4, then must use 1 + 1 → 3 coins. The optimum is 3 + 3 → 2 coins. Greedy commits to a big coin that ruins the remainder — this failure is the motivation for DP.

Approach 2 — Bottom-up DP over amounts

Define dp[a] = fewest coins to make amount a. To make a, the last coin used was some coin, leaving a smaller amount:

dp[a] = 1 + min(dp[a - coin]) over every coin that fits.

Fill from 0 upward; initialize with Infinity meaning "not yet reachable".

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

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

Time: O(amount × coins). Space: O(amount).

Infinity does double duty: it marks unreachable amounts, and Infinity + 1 is still Infinity, so unreachable states never contaminate reachable ones.

Approach 3 — Top-down memoized recursion

The same recurrence written as recursion with a cache: best(a) = 1 + min(best(a - coin)). Identical complexity; sometimes easier to derive under pressure. (BFS over amounts also works — each "level" is one more coin — a fun alternative to mention.)

Dry run

Approach 2 with the greedy-killer: coins = [1, 3, 4], amount = 6.

dp[6] = 2 (3 + 3) — the table considers every last-coin choice at every amount, which is exactly what greedy refused to do.

Edge cases

• amount = 0 → 0 coins (base case, not -1).
• Amount unreachable, e.g. coins = [2], amount = 3 → dp[3] stays Infinity → -1.
• A coin larger than the current amount is skipped by coin <= a.
• Counting ways instead of fewest (Coin Change II, LC 518) flips the loop order and the recurrence — related, but not the same table.