Head First Algorithms and Data Structures

Chapter 9. Dynamic Programming: Been There, Stored That

A Note for Early Release Readers

With Early Release ebooks, you get books in their earliest form—the author’s raw and unedited content as they write—so you can take advantage of these technologies long before the official release of these titles.

This will be the 9th chapter of the final book.

If you’d like to be actively involved in reviewing and commenting on this draft, please reach out to the editor at [e-mail].

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 ...