In this chapter, we’ll study four problems that appear to be solvable using recursion. As you’ll see, while in theory we can use recursion, in practice it leads to an explosion of work that renders the problems unsolvable. Not to worry: you’ll learn two powerful, related techniques, called memoization and dynamic programming, that will lead to shocking performance increases, morphing runtimes from hours or days to seconds. These techniques aren’t just for the four problems that I’ve selected for this chapter. Once you learn these techniques, you’ll be able to solve hundreds of other programming problems. If ...

Get Algorithmic Thinking now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.