You have a knapsack with limited space. Which items give you the most value? Dynamic programming tackles this kind of problem by solving smaller versions first, storing their answers, and using them to build up to the full answer. section 11.3 section 11.5
Fill a knapsack grid
Put items in the rows and knapsack capacities in the columns. Each cell asks: with these items and this much space, what is the best value so far? For a 1 lb guitar worth $1,500, the first 1 lb cell is $1,500. As you fill later rows, compare keeping the previous best with taking the new item and adding the best value that fits in the remaining space. section 11.3 section 11.5
A cell holds the best answer found for its smaller problem, so later choices can reuse it. Adding an item means adding a row, not starting the whole grid over. In the 4 lb example, a new item raises the best value from $3,500 to $4,000; the stored maximum never gets worse. section 11.5
To design a grid for a new problem, ask:
- What are you trying to optimize? That quantity usually goes in each cell. section 11.14
- What smaller problems lead to the answer? Their changing parts suggest the grid’s axes. section 11.15
- Can each choice be evaluated without changing the cost of other choices? The itinerary example breaks the simple grid approach when a shared trip makes later visits cheaper. section 11.11
From luggage to language
For a two-day visit, treat available time like knapsack capacity and give each attraction a duration and a value. For misspelled words, use the two words as grid axes: a cell records the length of a common substring for smaller pieces of those words. The grid changes, but the question stays the same: which smaller answers help you find the best larger one? section 11.10 section 11.15
Not every knapsack variant fits this take-or-leave-it grid. If you can take fractions of items, a greedy algorithm is offered instead. There is no single formula for every dynamic programming grid: choose subproblems that match the particular goal and constraint. section 11.9 section 11.20
