Coin change: why grabbing the biggest coin first can fail, and how a table fixes it

You are a cashier and a customer is owed 6 cents in change. Your drawer holds coins worth 1, 3 and 4 cents. What is the fewest number of coins you can hand over?

Most people start by grabbing the biggest coin that fits. That plan has a name, a greedy algorithm: at every step take whatever looks best right now and never look back. For 6 cents it gives a 4, then two 1s, which is three coins. But two 3s also make 6. The greedy plan was beaten by a coin it never considered.

When greedy works, and when it doesn't

With real US coins (1, 5, 10, 25) the biggest-first plan happens to give the fewest coins every time, so cashiers get away with it. That is a property of that particular set of coins, not of the plan. Here is the plan as code:

def greedy(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None

print(greedy([1, 3, 4], 6))
print(greedy([1, 5, 10, 25], 63))

Running it prints:

[4, 1, 1]
[25, 25, 10, 1, 1, 1]

The second answer (six coins for 63 cents) is the best possible. The first (three coins for 6) is not, because two 3s do it in two. A greedy plan commits to the 4 early, and that choice can't be undone.

The fix: answer the small questions first

Instead of committing, we can ask a smaller question: what is the fewest coins for every amount from 0 up to 6? We build the answers in order, and each new answer reuses the older ones.

Say we already know the best answer for every amount below 6. To make 6, the last coin we hand over is either a 1, a 3 or a 4. If it is a 4, we still owe 2, and we already know the best way to make 2. So the cost of "finish with a 4" is best(2) + 1. Do the same for each coin and keep the smallest:

• finish with a 1: best(5) + 1
• finish with a 3: best(3) + 1
• finish with a 4: best(2) + 1

This trick, solving small versions first and storing the answers in a table so each is computed once, is called dynamic programming. (The name is historical and doesn't mean much; think "filling in a table".) It is close kin to the notebook idea from memoization: never solve the same small problem twice.

Watch the table fill in

A cell marked × means that amount can't be made at all. With coins 4 and 5, nothing makes 7: a 4 leaves 3, a 5 leaves 2, and neither of those is reachable.

The same idea as code

def fewest_coins(coins, amount):
    best = [0] + [None] * amount      # best[a] = fewest coins that make a
    for a in range(1, amount + 1):
        options = [best[a - c] + 1 for c in coins
                   if c <= a and best[a - c] is not None]
        best[a] = min(options) if options else None
    return best

print(fewest_coins([1, 3, 4], 6))
print(fewest_coins([4, 5], 7))

Running it prints:

[0, 1, 2, 1, 1, 2, 2]
[0, None, None, None, 1, 1, None, None]

Read the first line as a table: 0 cents needs 0 coins, 3 cents needs 1, 6 cents needs 2. The loop looks at each amount once and tries each coin, so the work grows with amount × number of coins. Trying every combination instead would grow far faster.

So what, for your own code?

Two habits are worth taking away. First, when a "take the best thing right now" plan feels natural, test it against a small tricky case before trusting it. A few minutes with pencil and paper (or the figure above) can reveal that one early choice blocks a better one later. Second, when a problem can be split into smaller copies of itself and those copies overlap, store their answers. Spell-checkers measuring how different two words are, route planners, and text-diffing tools all use tables like this.

Greedy is not bad: it is fast and sometimes provably right, and plenty of real algorithms use it. The skill is knowing which problems allow it. When in doubt, build the table.