Why does the greedy approach fail for coin change?

Taking the largest coin first is not always optimal. With coins 1, 3, 4 and amount 6, greedy picks 4+1+1 (three coins) while the best is 3+3 (two).

What is the recurrence?

dp[a] = 1 + min(dp[a - c]) over every coin c not larger than a, with dp[0] = 0. Fill amounts from 0 up to the target.

What is the time and space complexity?

O(amount * number of coins) time and O(amount) space for the table.

What should be returned when the amount cannot be made?

Return -1. Initialise the table with infinity (or amount + 1) and convert any value that remains unreachable at the end.

How is counting the number of ways different?

The loop order changes: iterate coins on the outside and amounts on the inside to count combinations, and amounts outside to count ordered sequences. The recurrence adds instead of taking a minimum.

What are the edge cases?

Amount 0 returns 0 coins, an amount smaller than every coin returns -1, and a coin of value 0 must be rejected or it loops forever.

Coin change, and why greedy is wrong

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

Take the biggest coin first and you get the wrong answer: with [1, 3, 4] for 6, greedy picks 4+1+1 — three coins — where 3+3 is two. The fix is a table: best[a] = 1 + min(best[a - c]) over the coins that fit, in O(amount × coins).

Dynamic programmingCoding problemMedium

Step through it

Speed

What to watch

Every entry is built from a smaller amount, which is why filling upwards works.
Greedy commits to the 4 and cannot undo it.
Unreachable amounts stay at infinity and become −1.

Say this out loud

"Greedy does not work in general - with coins 1, 3, 4 and amount 6 it gives three coins where two is optimal. So a table: best[a] is one plus the minimum over best[a - c] for each coin c that fits, filled upwards from 0. O(amount times number of coins) time, O(amount) space. Greedy happens to be optimal for canonical systems like real currency, which is why the intuition is so strong."

def greedy(coins, amount): """Biggest coin first. Correct for some systems, not in general.""" used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): """best[a] = 1 + min(best[a - c]) over coins that fit.""" INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) # for reconstructing the coins for a in range(1, amount + 1): for c in coins: if c <= a and best[a - c] + 1 < best[a]: best[a] = best[a - c] + 1 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) coins, amount = [1, 3, 4], 6 g = greedy(coins, amount) n, used = fewest(coins, amount) print(f"coins {coins} amount {amount}") print(f" greedy : {g} -> {len(g)} coins") print(f" optimal: {used} -> {n} coins") print(" greedy loses because it commits to the 4 and cannot undo it")

def greedy(coins, amount): used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) for a in range(1, amount + 1): for c in coins: if c <= a and best[a - c] + 1 < best[a]: best[a] = best[a - c] + 1 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) # Greedy IS optimal for canonical systems - which is why the intuition sticks. print() print("real currency [1, 5, 10, 25]:") agree = True for amt in range(1, 100): gg = greedy([1, 5, 10, 25], amt) dd, _ = fewest([1, 5, 10, 25], amt) if len(gg) != dd: agree = False print(f" disagree at {amt}: greedy {len(gg)}, optimal {dd}") print(" greedy matches the optimum for every amount 1..99:", agree)

def greedy(coins, amount): used, left = [], amount for c in sorted(coins, reverse=True): while left >= c: left -= c used.append(c) return used if left == 0 else None def fewest(coins, amount): INF = float("inf") best = [0] + [INF] * amount pick = [None] * (amount + 1) for a in range(1, amount + 1): for c in coins: if c <= a and best[a - c] + 1 < best[a]: best[a] = best[a - c] + 1 pick[a] = c if best[amount] == INF: return -1, [] coins_used, a = [], amount while a > 0: coins_used.append(pick[a]) a -= pick[a] return int(best[amount]), sorted(coins_used) # The edges. print() print("amount 0 needs no coins:", fewest([1, 2, 5], 0)) print("unreachable amounts give -1:", fewest([5, 10], 3)) print("a single coin that fits exactly:", fewest([7], 7)) # Cost, and the word that matters. amount = 5_000 n, _ = fewest([1, 3, 4], amount) print() print(f"amount {amount:,} with 3 coins -> {n} coins") print(f" table entries filled: {amount:,} (amount x coins operations)") print(" note 'amount' is a VALUE, not a length: this is pseudo-polynomial")

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Coin change, and why greedy is wrong

Step through it

What to watch

Say this out loud

Overview

Run it

The counterexample is the answer

The recurrence, and the direction to fill it

Fewest coins versus how many ways

What it costs, and when it is too much

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself