11 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 how to come up with a dynamic programming solution to a new problem.

The knapsack problem (revisited)

Let’s revisit the knapsack problem from chapter 10. 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 ...

Get Grokking Algorithms, Second Edition 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.