Suppose you have a knapsack with a 4 lb limit and want to pack the most valuable items. What if you first solved the same problem for smaller knapsacks? Each smaller question is a subproblem. Dynamic programming uses its answers to build toward the answer for the full knapsack. section 11.3
A grid helps keep those questions straight. In the knapsack grid, rows represent the items available so far and columns represent weight limits. A cell asks for the best value possible with that row’s items and that column’s limit. Fill in the smaller cases, and their answers help you tackle larger ones. section 11.3 section 11.20
A different kind of smaller question
To compare a misspelled word with a possible match, you can compare shorter parts of the words first. Instead of starting with “hish” and “fish,” try “his” and “fis.” A grid cell can hold the length of the longest substring those parts have in common. Now the grid’s axes—parts of the two words—have a purpose. section 11.14 section 11.15
How do you spot useful subproblems? Ask what each cell should answer, then choose grid axes that describe the smaller cases. There is no single formula for every dynamic-programming problem; finding one takes experimentation. section 11.15 section 11.16 section 11.20
The smaller cases must be discrete: one choice must not change the cost of another in a way the subproblem leaves out. For example, visiting one Paris attraction makes another cheaper because the trip to Paris has already been paid for. Treating each visit as an independent item would count that travel time more than once. section 11.11
