Algorithmic Thinking

3 MEMOIZATION AND DYNAMIC PROGRAMMING

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