Greedy vs. Dynamic Programming: When the "Obvious" Answer Is Wrong

A greedy algorithm solves a problem the way its name suggests: at every single step, it takes whatever option looks best right now, never reconsidering that choice later, and never looking further ahead than the immediate decision in front of it. It's the most natural, intuitive way to approach a lot of problems, which is exactly why it's worth knowing precisely when that intuition holds up and when it quietly betrays you.

Making change is the classic example where the greedy, obvious-feeling approach genuinely works. With US coins — quarters, dimes, nickels, pennies — always picking the largest coin that doesn't overshoot the remaining amount happens to produce the fewest possible coins for any amount, every single time. That's not a coincidence of this specific problem being simple; it's a real, provable property of exactly this set of coin denominations.

Here's the part that surprises people: change a detail of the setup, and the same greedy strategy stops working, with no warning that anything went wrong. Imagine a currency with coins worth 1, 3, and 4, and the target amount is 6. Greedy picks the largest coin that fits first — a 4-coin — leaving 2 remaining, which then has to be made from two 1-coins, for a 3-coin total (4 + 1 + 1). But two 3-coins also make exactly 6, using only 2 coins total — genuinely fewer than the greedy answer found, and greedy never even considered it, because taking the biggest coin available at each step looked like the right move in the moment.

Dynamic programming is the more careful alternative for exactly this kind of problem: instead of committing to the locally best-looking choice and never revisiting it, it works through every smaller sub-problem methodically, keeping track of the actual best answer found for each one, and builds the full answer up from results it has already verified rather than results that merely looked good at the time. It costs more computation and more bookkeeping than a greedy approach, but it's guaranteed correct on problems where being locally greedy can lead somewhere provably worse, like the 1-3-4 coin example above.

The genuinely useful skill isn't memorizing which named problems need which approach — it's the habit of asking, before reaching for the obvious greedy solution, whether an early "best" choice could ever close off a better option later on. Making change with well-behaved coin denominations, or picking the shortest task first in some scheduling problems, are cases where the greedy choice is provably always safe. Anytime an early choice can't be undone and might block a better combination discovered later, that's the signal that dynamic programming's more careful, exhaustive bookkeeping is worth its extra cost.

Greedy: 4 + 1 + 1 = 3 coins  (takes the biggest coin first, gets stuck)
Actual best: 3 + 3 = 2 coins  (dynamic programming finds this; greedy never considers it)