Coin Change: Why Greedy Fails and Dynamic Programming Doesn't

Everyone already knows an algorithm for making change: hand over the biggest coin that fits, repeat. It is what a cashier does, it is fast, and for the coins in your pocket it gives the fewest coins every time. So when an interview asks for the minimum number of coins to make an amount, the natural first move is greedy — and on the right coin set it quietly returns the wrong answer.

This article shows exactly where that happens, why a small table fixes it, and how to tell in advance whether a coin set is safe for greedy.

The problem it solves

Given coin values (with unlimited copies of each) and a target amount, return the fewest coins that sum exactly to the target, or report that no combination does.

Three small cases cover everything interesting:

• Coins 1, 3, 4 and target 6. Greedy takes 4, then 1, then 1 — three coins. But 3 + 3 is two.
• Coins 5, 2 and target 6. Greedy takes 5 and is stuck with 1 left, so it reports failure. But 2 + 2 + 2 works.
• Coins 4, 6 and target 7. Nothing works — every combination is even — and the answer has to say so.

The intuition

Greedy fails because it commits. Taking the 4 feels like progress, but it leaves a remainder of 2 that can only be paid in ones. The better answer needed a smaller first coin, and greedy never looks back to consider it.

The fix is to stop guessing the first coin and try all of them — without paying for it exponentially. Think about the last coin in an optimal answer for amount a. If that coin is c, the coins before it must be an optimal answer for a − c; if they were not, you could swap in a better set and beat the "optimal" answer. So:

The fewest coins for a is one more than the fewest coins for a − c, for whichever coin c makes that smallest.

That only refers to smaller amounts. Fill a table from 0 upwards — amount 0 needs zero coins, and each later cell looks back at a few earlier ones — and by the time you reach the target, every cell it needs is already settled. An amount no coin combination can reach simply stays at infinity, which is how the function knows to report failure rather than inventing an answer.

The table is also why the problem is DP rather than search. Amount 12 with coins 1, 3, 4 can be reached through many different sequences, but they all hand the rest of the problem the same subproblem. The table solves each amount once.

Watch it run

The top row fills amounts 0 to 6 for coins 1, 3, 4; watch amount 6 settle on 2 by stepping back to amount 3, where greedy would have stepped back to 2. The bottom row runs coins 4, 6 up to 7 and shows 7 staying at ∞.

The code

Both versions side by side, with the DP recording which coin won each amount so the actual coins can be read back out:

def greedy(coins, target):
    used = []
    for c in sorted(coins, reverse=True):
        while target >= c:              # take the biggest coin that still fits
            target -= c
            used.append(c)
    return used if target == 0 else None

def fewest(coins, target):
    INF = float("inf")
    best = [0] + [INF] * target         # best[a] = fewest coins summing to a
    last = [0] * (target + 1)           # which coin achieved best[a]
    for a in range(1, target + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a], last[a] = best[a - c] + 1, c
    if best[target] == INF:
        return None
    used = []
    while target:                       # walk the winning coins back to 0
        used.append(last[target])
        target -= last[target]
    return used

print(greedy([1, 3, 4], 6), fewest([1, 3, 4], 6))    # [4, 1, 1] [3, 3]
print(greedy([4, 6], 7), fewest([4, 6], 7))          # None None
print(greedy([5, 2], 6), fewest([5, 2], 6))          # None [2, 2, 2]
print(len(fewest([1, 5, 10, 25], 99)))               # 9

The DP is short enough to get subtly wrong, so it is checked against an exhaustive search that tries every count of every coin:

import random
from functools import lru_cache

def brute(coins, target):
    @lru_cache(maxsize=None)
    def go(i, left):                    # try every count of coins[i], then move on
        if left == 0:
            return 0
        if i == len(coins):
            return float("inf")
        return min(k + go(i + 1, left - k * coins[i])
                   for k in range(left // coins[i] + 1))
    ans = go(0, target)
    return None if ans == float("inf") else ans

random.seed(3)
ok = True
for _ in range(3000):
    coins = random.sample(range(1, 15), random.randint(1, 4))
    t = random.randint(0, 40)
    got = fewest(coins, t)
    ok &= (None if got is None else len(got)) == brute(coins, t)
print(ok)                                            # True

Three thousand random coin sets and targets, including unreachable ones and a target of 0, all agreeing.

When greedy is actually safe

Greedy is not always wrong. For a given coin set it either matches the DP on every amount or fails somewhere, and you can find out by asking:

def first_greedy_failure(coins, limit):
    for t in range(1, limit + 1):
        g, d = greedy(coins, t), fewest(coins, t)
        if (g and len(g)) != (d and len(d)):
            return t
    return None

print(first_greedy_failure([1, 5, 10, 25], 1000))    # None
print(first_greedy_failure([1, 3, 4], 1000))         # 6
print(first_greedy_failure([1, 5, 12], 1000))        # 15

random.seed(5)
worst = 0
for _ in range(2000):
    coins = [1] + random.sample(range(2, 30), random.randint(1, 3))
    two = sum(sorted(coins)[-2:])
    t = first_greedy_failure(coins, 200)
    if t is not None:
        worst = max(worst, t / two)
print(worst < 1)                                     # True

Everyday denominations pass up to 1,000. The last check shows how far you need to look: across 2,000 random coin sets, every first failure appeared below the sum of the two largest coins. That agrees with a published bound (Kozen and Zaks, 1994), so a finite scan is a real proof for one coin set, not a hope.

The complexity

The table has target + 1 cells and each tries every coin: O(target × k) time for k coins and O(target) memory. Note that this is pseudo-polynomial — it grows with the numeric value of the target, not with the length of the input. A target of a billion is a billion cells even though it takes ten digits to write down.

Greedy is O(k log k) for the sort plus one step per coin handed out. That speed is exactly why it is tempting.

Where it goes wrong

• Using greedy without checking the coin set. Fine for standard currency; wrong for arbitrary input, which is what an interview gives you.
• Initialising with 0 instead of infinity. Every amount then starts out "solved" with zero coins, nothing can improve on that, and the function answers 0 for every target.
• Confusing it with the counting version. "How many ways" sums over coins instead of taking a minimum, and the loop order decides whether 1 + 2 and 2 + 1 are counted once or twice — see coin change ways.
• Returning the table value without a sentinel check. Returning inf where the caller expects -1 or None is a classic bug.

How to say it in an interview

"Greedy works for some coin sets but not in general — with 1, 3 and 4, greedy makes 6 with three coins while 3 + 3 is two. So I'll build a table from 0 to the target, where each amount is one more than the best of amount-minus-coin over all coins. Unreachable amounts stay at infinity. That's O(amount × coins) time and O(amount) space."

Leading with the counterexample is what makes the DP feel necessary rather than memorised.