Head First Algorithms and Data Structures

Chapter 9. Dynamic Programming: Been There, Stored That

You’ve seen greedy algorithms make fast decisions. But what do you do when greedy gives the wrong answer and you know brute force takes forever? You need an algorithm that’s both smart and thorough, one that works through all the options without wasting time on work it’s already done. That’s dynamic programming: the art of solving hard problems by remembering what you’ve already figured out. Dynamic programming shows up everywhere: route planning, spell checkers, financial optimization, DNA sequencing, and scheduling. It’s the technique that turns “we’d need a supercomputer running for years” into “done in milliseconds on your laptop.” If you’ve ever wondered how software finds the best option among billions of possibilities without actually checking billions of possibilities, this is how. Once you see the pattern, you’ll start recognizing it in problems you thought were unsolvable. But first, we’re going to break greedy—and show you why that’s a good thing.

When greedy fails

All cashiers at Algorithm Land are trained to give the least amount of change as possible. Fewer coins equals faster lines equals happier customers.

Problem is, Algorithm Land doesn’t use US coins. They have their own tokens in denominations of 1, 7, and 10.

A cashier owes you 14 in change. She falls back on her US coin training: always pick the ...