Why greedy fails on Coin Change, and the DP that fixes it

Hand the Coin Change problem to a fresh candidate and most of them reach for greedy: take the largest coin that fits, subtract, repeat until you hit zero. With US currency that actually works, which is exactly why it’s a trap. The interviewer hands you a set of denominations where greedy quietly returns the wrong answer, and now you’re defending a strategy that was never correct to begin with.

Here’s the case that breaks it. Coins worth 1, 3, and 4, and you need to make 6. Greedy grabs the 4, then has to make 2 out of {1, 3}, so it takes two 1s: three coins total. The real answer is 3 + 3, two coins. Greedy never considered skipping the 4 because it only ever looks one step ahead.

The actual problem (LeetCode 322) reads like this: given an array of coin denominations and a target amount, return the fewest coins that sum to the amount, assuming an unlimited supply of each. If no combination works, return -1. That last clause matters, and people forget it under pressure.

Greedy can’t be patched, so stop trying

The reflex after seeing the counterexample is to add a tweak: sort differently, try the second-largest when the largest fails, sprinkle in a little backtracking. Resist it. Greedy is correct on Coin Change only when the denomination system is canonical, meaning the largest-first rule provably never loses. US coins (1, 5, 10, 25) happen to be canonical. An arbitrary set handed to you in an interview is not, and there’s no cheap local rule that rescues it. You have to weigh every way of reaching the amount, and that’s the cue for dynamic programming.

The recurrence in one line

Define dp[a] as the fewest coins needed to make amount a. The base case is dp[0] = 0: zero coins make zero. For any larger amount you try each coin c, look at how many coins it took to make a - c, and add one for the coin you just spent:

dp[a] = min(dp[a - c] + 1) for every coin c where c <= a

If no coin leads to a reachable sub-amount, a is impossible and dp[a] stays at infinity. Bottom-up, that’s a short double loop:

def coin_change(coins, amount):
    INF = amount + 1            # bigger than any real answer (worst case is amount 1s)
    dp = [0] + [INF] * amount   # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Using amount + 1 as the stand-in for infinity is a small move that pays off. The most coins you could ever need is amount itself (all 1s, when a 1 exists), so any genuine answer is strictly smaller, and you skip the bother of doing arithmetic on float('inf'). Time cost is O(amount * len(coins)), space is O(amount). Both are about as good as this problem allows.

Plenty of people write the top-down version instead: a recursive solve(remaining) that returns the best for a remaining amount, memoized in a dictionary. It computes the same values with the same big-O, and some find the recursion easier to picture. The thing to watch is stack depth when the amount is large and your smallest coin is 1, since the recursion can descend as far as the amount. The bottom-up table avoids that, which is why I reach for it first.

The unbounded part, and why it is the whole point

This is the unbounded knapsack pattern, and the word that earns its keep is unbounded. Each coin can be used as many times as you like. Look at the inner loop: when you compute dp[a] from dp[a - c], the sub-solution dp[a - c] is allowed to have already used coin c. Nothing stops it. That reuse is free, and it’s what separates this from the 0/1 knapsack, where each item exists once and you must guard against picking it twice.

If you’ve seen 0/1 knapsack coded with the amount loop running backward, that backward sweep is there precisely to block reuse. Coin Change runs the amount loop forward, which permits reuse. Same skeleton, opposite intent. An interviewer who knows the family will sometimes ask you to flip one form into the other on the spot, and the loop direction is the answer they’re listening for.

When they ask which coins, not how many

A frequent follow-up: don’t just give me the count, tell me the actual coins. Keep a second array recording, for each amount, the last coin that produced its best answer, then walk backward from the target.

def coin_change_with_coins(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    pick = [-1] * (amount + 1)         # the coin that set dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c
    if dp[amount] == INF:
        return -1, []
    used, a = [], amount
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[amount], used

That backtracking step is O(answer), cheap next to filling the table. If they push further and want every optimal combination rather than one of them, that’s a different and much bigger problem, and the right move is to say so out loud instead of bolting it onto this code.

Coin Change II and the loop order that catches everyone

The sister problem, LeetCode 518, flips the question: instead of the fewest coins, count how many distinct combinations sum to the amount. The recurrence looks almost the same, and that resemblance is where candidates fall in.

def coin_change_2(coins, amount):
    dp = [1] + [0] * amount      # dp[0] = 1: exactly one way to make zero
    for c in coins:              # coins on the OUTER loop
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

Put the coins on the outer loop and the amount on the inner, and you count combinations: {1, 1, 3} is the same multiset as {3, 1, 1}, counted once. Swap the loops so amount is outer, and you start counting ordered sequences, so {1, 3} and {3, 1} both register and the total balloons. Two lines reordered, completely different meaning. Being able to explain why shows the interviewer you understand the iteration rather than having memorized a template.

What they’re actually checking

The problem looks like it’s about coins. It isn’t. The interviewer wants to see whether you catch that greedy is unsafe, whether you can write a clean recurrence with a correct base case and a sane impossible-sentinel, and whether you can state the complexity without flailing. Land the 1, 3, 4 insight quickly and the rest tends to follow.

The follow-ups worth rehearsing come in a few shapes. A limited supply per coin turns this into bounded knapsack, and the forward-reuse trick stops being valid. A target in the billions with only a handful of coins makes the O(amount) table hopeless, and the conversation shifts toward BFS over reachable states or a number-theoretic shortcut. The count-versus-minimize split is the one that separates people who learned the pattern from people who matched the keywords. Know which loop order goes with which question and you’ll be ready for whichever variant lands in your round.