Canonical Deep-Dive: Coin Change

Problem: Coin Change (https://leetcode.com/problems/coin-change/) The lesson: the five-step DP framework, on a problem where the obvious greedy idea fails.

This is a guided walk-through, not an answer key. It explains how to think through the five steps of dynamic programming and shows you the recurrence as a relation, the base case, and the iteration order in words. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given a list of coin denominations coins and a target amount. Return the fewest number of coins that sum exactly to amount. You may use each denomination any number of times. If no combination sums to amount, return -1. The amount can be 0, in which case the answer is 0 (use no coins).

Why the obvious greedy idea fails

The first instinct most people have is greedy: always take the largest coin that still fits, then repeat on the remainder. For some coin systems (like US currency) that happens to work, which is exactly why it is a trap. It is not correct in general.

Concrete counterexample. Coins [1, 3, 4], amount 6. Greedy takes the largest coin that fits, 4, leaving 2; then 1 and 1, for a total of three coins (4 + 1 + 1). But the optimal answer is two coins: 3 + 3. Greedy committed to the 4 too early and could not see that two threes were better.

The lesson: when a locally optimal choice can foreclose a globally better one, greedy is unsafe, and you need to consider the choices systematically. That is what DP does.

The brute-force baseline

Before optimizing, have a baseline. The recursive brute force: to make amount, try each coin c, and recursively solve amount - c; the answer for amount is one plus the best of those subresults. The base cases are “amount 0 needs 0 coins” and “a negative amount is impossible.”

  • Time: exponential. The same subamount (say, “make 6”) gets recomputed through many different sequences of choices.
  • Space: O(amount) for the recursion stack depth.

Write this and watch it crawl on a moderate amount. The exponential cost comes entirely from recomputing the same subproblems, and that repetition is the signal to memoize. That signal is the recognition cue for the whole week.

The five-step framework

This is the recipe. Walk it in order, every time.

1. State. Define one quantity indexed by one number:

dp[a] is the fewest coins that sum exactly to amount a.

Say that sentence out loud before writing anything. If you can define the state cleanly, the rest follows. If you cannot, you do not yet understand the problem.

2. Transition (the recurrence). To make amount a, the last coin you place is some denomination c with c <= a. Whatever that last coin is, the rest of the amount, a - c, must itself be made optimally. So the fewest coins for a is one plus the best over all usable coins:

dp[a] = 1 + min( dp[a - c]  for each coin c where c <= a and dp[a - c] is reachable )

If no coin leads to a reachable smaller amount, a itself is unreachable. This is the unbounded-knapsack shape: because each coin may be reused, a - c is allowed to use the same coin c again, and nothing forbids it.

3. Base case.

dp[0] = 0. Amount zero needs zero coins.

Every other cell starts as “unreachable”, which you represent with float('inf') (larger than any real coin count), so that the min in the transition replaces it the moment a real combination appears.

4. Order of computation. The transition for dp[a] reads cells dp[a - c], which are all strictly smaller than a. So fill the table from small to large: compute dp[1], then dp[2], up to dp[amount]. By the time you reach a, every cell the transition needs is already final. (The top-down equivalent is the same recurrence written as a recursive function with @lru_cache; memoization fills the same subproblems on demand instead of in a sweep.)

5. Answer extraction. The answer is the single cell dp[amount]. With one correction for impossibility: if dp[amount] is still float('inf') at the end (no combination ever reached it), the problem says return -1.

The key insight, in one sentence

The fewest coins to make an amount is one more than the fewest coins to make that amount minus a single coin, minimized over which coin you remove; you compute every subamount once, smallest first, and reuse it. That reuse is what turns the exponential brute force into a single linear sweep over the amounts with a small inner loop over coins.

Exact complexity

  • Time: O(amount * len(coins)). There are amount + 1 cells, and each cell does O(len(coins)) work scanning the denominations. There is no hidden sort or extra factor.
  • Space: O(amount) for the one-dimensional dp table. (Unlike Climbing Stairs, you cannot drop to a constant number of rolling variables here, because the transition can read a cell as far back as amount - min(coins), so you must keep the whole table.)

Your work this week

  1. Implement Coin Change yourself, bottom-up, in your own work repo (for example coin-change.py). Define the dp table, set the base case, fill it small to large, and extract the answer with the -1 correction. Do not copy a solution; build it from the five steps above.
  2. Then write the top-down memoized version of the same recurrence (recursion plus @lru_cache). Confirm both give the same answers on the provided examples; convince yourself they are the same algorithm with different bookkeeping.
  3. Run both against the provided examples in practice/-style local tests, then submit to LeetCode’s judge. Test the edge cases yourself: amount = 0 (answer 0), a single coin that cannot tile the amount (answer -1), and a large amount near the constraint to feel the O(amount * len(coins)) cost.
  4. Commit with a five-question debrief in the message. In answer 3, state the exact complexity above and why you cannot reduce the space to O(1) here.

When you can explain, from memory and with no AI open, the five steps for this problem (state, transition, base case, order, answer) and why greedy fails on [1, 3, 4] making 6, you own this problem. That explanation is exactly what an interviewer will ask for, and it is the template you will reuse on every DP problem this week and next.