Algorithmic Thinking, 2nd Edition

4ADVANCED MEMOIZATION AND DYNAMIC PROGRAMMING

In this chapter, we’re going to continue with memoization and dynamic programming. You don’t need to read this chapter to continue through the book. But there’s more to learn if you’d like to deepen your understanding. We’ll see how to make a dynamic-programming problem easier through a change in perspective, work with more than two dimensions in our subproblem arrays, and stretch our skills to go beyond the “optimize the solution” problems we’ve seen thus far. We’ll also get a bit more practice with the fundamentals. You’ll be a dynamic-programming rock star after this.

Problem 1: The Jumper

We’ll ...