Algorithmic Thinking, 2nd Edition

3MEMOIZATION AND DYNAMIC PROGRAMMING

In this chapter, we’ll study three 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. In the next chapter, we’ll level up and solve two even more challenging problems using these techniques. Once you get the hang of this stuff, you’ll be able to solve hundreds of other programming ...