Grokking Algorithms

Chapter 9. Dynamic programming

In this chapter

• You learn dynamic programming, a technique to solve a hard problem by breaking it up into subproblems and solving those subproblems first.
• Using examples, you learn to how to come up with a dynamic programming solution to a new problem.

The knapsack problem

Let’s revisit the knapsack problem from chapter 8. You’re a thief with a knapsack that can carry 4 lb of goods.

You have three items that you can put into the knapsack.

What items should you steal so that you steal the maximum money’s worth ...