Coin Change

Given coin denominations (unlimited supply of each) and a target amount, return the fewest coins that sum to exactly the amount, or -1 if it cannot be done. (LC 322)

Nothing else in the circuit is dynamic programming, so this is the one to learn the shape from. Every DP answer has the same four parts, and this problem shows them clearly.

The recipe

Say before you type: "The fewest coins for amount a is one coin plus the fewest for whatever remains after that coin. I don't know which coin is best, so I try all of them. I solve every amount from 0 up, so the smaller answers I need are always already there."

1. State: best[a] is the fewest coins that make exactly a.
2. Base case: best[0] = 0. Everything else starts at Infinity, meaning "not reachable yet".
3. Transition: for each amount a and each coin c <= a, best[a] = min(best[a], best[a - c] + 1).
4. Order: a from 1 up to amount, so best[a - c] is always computed before you read it.
5. Answer: best[amount], or -1 if it is still Infinity.

The code

function coinChange(coins: number[], amount: number): number {
  const best = new Array<number>(amount + 1).fill(Infinity);
  best[0] = 0; // zero coins make zero

  for (let a = 1; a <= amount; a++)
    for (const coin of coins)
      if (coin <= a && best[a - coin] + 1 < best[a]) best[a] = best[a - coin] + 1;

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

Why this shape

The greedy answer (take the biggest coin you can, repeat) is the one everyone reaches for, and it is wrong. With coins [1, 3, 4] and an amount of 6, greedy takes 4 + 1 + 1 = three coins, but 3 + 3 is two. When the best choice now depends on what is left, you have to compare, and the table is how you compare without redoing work.

Without the table, the recursion f(a) = 1 + min(f(a - c)) recomputes the same amounts exponentially many times. The table solves each amount exactly once.

Infinity is the right "unreachable" value because Infinity + 1 is still Infinity, so an unreachable amount never beats a real one in the min. A value like -1 would win every comparison and poison the table.

Complexity

	Cost	Because
Time	O(amount · coins)	Every amount tries every coin
Space	O(amount)	One table entry per amount

Traps

• Greedy. Test it on [1,3,4], 6 and [1,5,6,9], 11 before you trust it. Name the counterexample out loud.
• A -1 sentinel inside the table. Use Infinity for unreachable and convert once, at the end.
• The table is amount + 1 long. You need an index for amount itself, and one for 0.
• The coin <= a guard. Without it, a - coin goes negative and reads off the front of the array.
• Amount 0. The answer is 0, not -1. The base case handles it if you did not special-case it away.
• Top-down recursion. It works with a memo, but on a 10,000 amount of 1s the recursion goes ten thousand deep. Bottom-up has no such limit.

Same problem, as a graph

Think of each amount as a node and each coin as a move. The question becomes "how few moves from 0 to the target", which is BFS. Each level is one more coin.

function coinChange(coins: number[], amount: number): number {
  if (amount === 0) return 0;
  const seen = new Array<boolean>(amount + 1).fill(false);
  seen[0] = true;
  let frontier = [0], steps = 0;
  while (frontier.length) {
    steps++;
    const next: number[] = [];
    for (const a of frontier)
      for (const coin of coins) {
        const b = a + coin;
        if (b === amount) return steps;
        if (b < amount && !seen[b]) { seen[b] = true; next.push(b); }
      }
    frontier = next;
  }
  return -1;
}

Same answer, same cost, and it connects this problem to the traversals you already know. Offer it as the second approach.

The pattern this trains

Every DP problem is state, base case, transition and order. Climbing Stairs (70) and House Robber (198) are the one-coin warm-ups. Coin Change II (518) counts the ways instead, and there the loop order matters: coins outside, amounts inside. Perfect Squares (279) is this problem with the coins being square numbers. The trigger is "fewest", "minimum" or "how many ways" where the best choice now depends on what is left.