Chapter 11: Dynamic programming
The introduction defines dynamic programming as solving a hard problem by first solving smaller subproblems.
After this chapter you will be able to
- Dynamic programming’s basic idea. Explain that dynamic programming tackles a hard problem by breaking it into subproblems and solving those subproblems first.
- Knapsack choice and constraint. Describe the knapsack problem posed here: choose from three items to maximize the value stolen without exceeding a 4 lb carrying limit.
- Exhaustive search tradeoff. Explain how trying every possible set of goods finds the highest-value set, and why the number of sets makes this approach impractical.
- Knapsack grid and subproblems. Explain what the grid’s rows and columns represent and why the algorithm fills in smaller knapsack capacities before solving the 4 lb problem.
- Cell comparisons and leftover space. Describe how a cell keeps or improves the previous best value, including how a smaller-capacity answer accounts for space left after adding an item. Apply this to the laptop-and-guitar result.
- Adding a new item row. Explain how to account for the iPhone by adding a row rather than recalculating the whole grid, comparing each old maximum with a combination that includes the iPhone.
- Knapsack Row Order. Explain that filling the knapsack grid with the stereo, laptop, and guitar rows in a different order gives the same answer.
- Finer knapsack weight increments. Explain why adding a 0.5 lb necklace means the existing knapsack grid must change.
- Fractional item limitation. Explain why the dynamic programming solution described for the knapsack problem cannot handle taking part of an item.
- Greedy fractional selection. Describe how the section solves the fractional-item problem by repeatedly taking as much as possible of the highest-value item per pound, then moving to the next.
- Travel itinerary knapsack mapping. Explain how the sightseeing problem maps to the knapsack problem: available time is the limit, places are the items, visit durations determine how much time they use, and ratings express how much you want to see them.
- Dependent itinerary item costs. Explain why adding Paris attractions breaks the knapsack approach used for the itinerary: travel to Paris is paid once, so an attraction’s time cost depends on whether another Paris attraction is already included.
- Nested sub-knapsack combinations. Explain why combining at most two sub-knapsacks at a time does not limit the best solution to two stolen items.
- Unused Knapsack Capacity. Explain why an optimal knapsack choice need not fill all available space, using the diamond example.
- Dynamic programming problem conditions. Explain that dynamic programming is useful for optimizing something under a constraint when the problem can be divided into discrete subproblems that do not depend on each other.
- Grid cells as subproblems. Describe how picturing a dynamic programming problem as a grid helps: cells represent subproblems, their values are usually what is being optimized, and dividing the problem into subproblems helps determine the axes.
- Longest Common Substring Grid. Describe how to set up a grid for the longest common substring problem: use the two words as axes, compare smaller substrings as subproblems, and put the length of the longest shared substring in each cell.
- Finding a grid formula. Explain why the section encourages experimenting with a formula rather than following a ready-made recipe, and distinguish the known example answer from a rule that fills the grid.
- Reading substring grid results. Explain why the longest common substring is found by taking the largest number anywhere in the grid, rather than necessarily reading the last cell. Apply that result to compare fish and vista with hish.
- Substring and subsequence comparison. Explain why the longest common substring does not distinguish whether “fosh” is closer to “fish” or “fort,” and describe how the longest common subsequence compares the words instead.
- Practical dynamic programming uses. Describe the examples of dynamic programming given here: longest common subsequence for comparing DNA, diff for finding differences between files, and Levenshtein distance for measuring string similarity.
- Constrained optimization and subproblems. Explain that dynamic programming is useful for optimizing something under a constraint when the problem can be broken into discrete subproblems.
- Grid cells and solution values. Describe how a dynamic programming grid represents subproblems and the values being optimized, and state that there is no single formula for every solution.
What it builds on
- The knapsack problem (chapter 10) · This section revisits the earlier knapsack problem.
- Approximation algorithms (chapter 10) · The earlier introduction to approximation algorithms.
Section by section
Introduction
The introduction defines dynamic programming as solving a hard problem by first solving smaller subproblems.
- Dynamic programming’s basic idea: Explain that dynamic programming tackles a hard problem by breaking it into subproblems and solving those subproblems first.
Why it matters: This basic idea frames the examples that follow in the chapter.
Key terms: dynamic programming, subproblems
11.1 The knapsack problem (revisited)
This section sets up the knapsack problem as choosing the most valuable goods a thief can carry within a weight limit.
- Knapsack choice and constraint: Describe the knapsack problem posed here: choose from three items to maximize the value stolen without exceeding a 4 lb carrying limit.
Why it matters: The weight limit and value objective define the problem the following sections solve.
Key terms: knapsack, 4 lb, maximum money’s worth
11.2 The simple solution
The section presents exhaustive search as a way to find the most valuable set of goods and explains why its exponential running time makes it impractical.
- Exhaustive search tradeoff: Explain how trying every possible set of goods finds the highest-value set, and why the number of sets makes this approach impractical.
Why it matters: This explains why finding the best answer by brute force is not practical for many goods. - Approximation versus optimality: Distinguish the approximate solution mentioned from an optimal solution.
Why it matters: A fast answer that is close to the best is not necessarily the best answer.
Key terms: possible set of goods, most value, O(2n) time, approximate solution, optimal solution
11.3 Dynamic programming
The section builds a knapsack grid from smaller-capacity solutions and uses it to find the most valuable combination of items.
- Knapsack grid and subproblems: Explain what the grid’s rows and columns represent and why the algorithm fills in smaller knapsack capacities before solving the 4 lb problem.
Why it matters: The grid makes clear which smaller answers are available when evaluating a larger knapsack. - Cell comparisons and leftover space: Describe how a cell keeps or improves the previous best value, including how a smaller-capacity answer accounts for space left after adding an item. Apply this to the laptop-and-guitar result.
Why it matters: Reusing the answer for leftover space is what lets the grid find a better combination than either item alone.
Key terms: dynamic programming, grid, sub-knapsacks, rows, columns, max value, old estimate, space left over, subproblems
11.4 Knapsack problem FAQ
11.5 What happens if you add an item?
The section shows how to add an item to a dynamic-programming knapsack grid and why the best recorded value cannot decrease.
- Adding a new item row: Explain how to account for the iPhone by adding a row rather than recalculating the whole grid, comparing each old maximum with a combination that includes the iPhone.
Why it matters: You can extend a completed knapsack grid when a new item appears without starting over. - Nondecreasing maximum estimates: Explain why adding a new item cannot make a column’s recorded maximum value go down.
Why it matters: This explains why a new item can improve a knapsack result but cannot spoil an existing best result.
Key terms: dynamic programming, max value, subproblem, row, current max estimate, column
11.6 What happens if you change the order of the rows?
Shows that changing the order of item rows in the knapsack grid does not change the answer.
- Knapsack Row Order: Explain that filling the knapsack grid with the stereo, laptop, and guitar rows in a different order gives the same answer.
Why it matters: You can arrange the item rows differently without changing the result.
Key terms: grid, rows
11.7 Can you fill in the grid column-wise instead of row-wise?
11.8 What happens if you add a smaller item?
Adding an item with a smaller weight shows why the knapsack grid may need finer weight increments.
- Finer knapsack weight increments: Explain why adding a 0.5 lb necklace means the existing knapsack grid must change.
Why it matters: A grid cannot answer a capacity question it was not built to represent.
Key terms: grid, finer granularity, 3.5 lb knapsack
11.9 Can you steal fractions of an item?
The section explains why the all-or-nothing dynamic programming solution does not handle fractional items and shows how a greedy approach does.
- Fractional item limitation: Explain why the dynamic programming solution described for the knapsack problem cannot handle taking part of an item.
Why it matters: It helps you recognize when the earlier knapsack solution does not fit the problem. - Greedy fractional selection: Describe how the section solves the fractional-item problem by repeatedly taking as much as possible of the highest-value item per pound, then moving to the next.
Why it matters: It gives you a way to choose what to carry when taking fractions is allowed.
Key terms: dynamic programming, fraction of an item, greedy algorithm, most valuable item, per pound
11.10 Optimizing your travel itinerary
The section recasts a two-day sightseeing itinerary as a knapsack problem that can be represented with a dynamic programming grid.
- Travel itinerary knapsack mapping: Explain how the sightseeing problem maps to the knapsack problem: available time is the limit, places are the items, visit durations determine how much time they use, and ratings express how much you want to see them.
Why it matters: Recognizing the same problem in a new setting lets you use the dynamic programming grid for a travel plan.
Key terms: knapsack problem, limited amount of time, dynamic programming grid
11.11 Handling items that depend on each other
This section uses a Paris itinerary to show why the knapsack dynamic-programming approach cannot handle items whose costs depend on other chosen items.
- Dependent itinerary item costs: Explain why adding Paris attractions breaks the knapsack approach used for the itinerary: travel to Paris is paid once, so an attraction’s time cost depends on whether another Paris attraction is already included.
Why it matters: Shared travel time shows why treating every attraction as an independent item gives the wrong itinerary cost.
Key terms: dynamic programming, subproblems, discrete, knapsack
11.12 Is it possible that the solution will require more than two sub-knapsacks?
This section explains how a solution can include more than two items even though the algorithm combines at most two sub-knapsacks at a time.
- Nested sub-knapsack combinations: Explain why combining at most two sub-knapsacks at a time does not limit the best solution to two stolen items.
Why it matters: It resolves the apparent conflict between a two-part combination and a solution containing many items.
Key terms: sub-knapsacks, best solution
11.13 Is it possible that the best solution doesn’t fill the knapsack completely?
A valuable diamond shows that the best knapsack choice can leave unused space.
- Unused Knapsack Capacity: Explain why an optimal knapsack choice need not fill all available space, using the diamond example.
Why it matters: Unused capacity does not mean you chose the wrong items.
Key terms: knapsack, value
11.14 Longest common substring
The section summarizes when dynamic programming is useful and gives a grid-based way to think about its subproblems before introducing a word-matching example.
- Dynamic programming problem conditions: Explain that dynamic programming is useful for optimizing something under a constraint when the problem can be divided into discrete subproblems that do not depend on each other.
Why it matters: These conditions help you recognize when dynamic programming may be useful. - Grid cells as subproblems: Describe how picturing a dynamic programming problem as a grid helps: cells represent subproblems, their values are usually what is being optimized, and dividing the problem into subproblems helps determine the axes.
Why it matters: Thinking in terms of subproblems gives you a way to start designing a dynamic programming grid.
Key terms: dynamic programming, constraint, discrete subproblems, grid, cells, subproblem, axes
11.15 Making the grid
The section sketches a dynamic-programming grid for finding the longest substring shared by two words.
- Longest Common Substring Grid: Describe how to set up a grid for the longest common substring problem: use the two words as axes, compare smaller substrings as subproblems, and put the length of the longest shared substring in each cell.
Why it matters: Choosing what each cell represents makes the larger word comparison manageable as smaller comparisons.
Key terms: dynamic programming, grid, cells, subproblems, longest substring
11.16 Filling in the grid
This section frames filling the longest-common-substring grid as a matter of finding a rule for its subproblems, but leaves the rule itself for the reader to try and the next section to explain.
- Grid cells as subproblems: Explain that each grid cell holds the value of a subproblem, and that finding a rule for those values is the task at hand.
Why it matters: Thinking of cells as subproblem results gives the reader a starting point for making sense of the grid. - Finding a grid formula: Explain why the section encourages experimenting with a formula rather than following a ready-made recipe, and distinguish the known example answer from a rule that fills the grid.
Why it matters: It separates checking a known answer from discovering a rule that works across the grid.
Key terms: grid, cell, subproblem, formula, framework, substring
11.17 The solution
The section shows how to read the completed longest-common-substring grid to decide which word Alex probably meant.
- Reading substring grid results: Explain why the longest common substring is found by taking the largest number anywhere in the grid, rather than necessarily reading the last cell. Apply that result to compare fish and vista with hish.
Why it matters: Reading the right cell lets you use the grid to choose the closer match.
Key terms: longest common substring, grid, last cell
11.18 Longest common subsequence
This section uses a misspelled-word example to show why the longest common subsequence can be more useful than the longest common substring for comparing words.
- Substring and subsequence comparison: Explain why the longest common substring does not distinguish whether “fosh” is closer to “fish” or “fort,” and describe how the longest common subsequence compares the words instead.
Why it matters: It shows why changing what you measure can resolve a comparison that a substring score leaves tied.
Key terms: longest common substring, longest common subsequence
11.19 Longest common subsequence—solution
The section presents the longest common subsequence solution and gives examples of dynamic programming in real-world use.
- Practical dynamic programming uses: Describe the examples of dynamic programming given here: longest common subsequence for comparing DNA, diff for finding differences between files, and Levenshtein distance for measuring string similarity.
Why it matters: These examples show that dynamic programming is useful beyond the knapsack problem.
Key terms: dynamic programming, longest common subsequence, diff, Levenshtein distance
11.20 Recap
The recap summarizes when dynamic programming is useful and how its grid represents an optimization problem as subproblems.
- Constrained optimization and subproblems: Explain that dynamic programming is useful for optimizing something under a constraint when the problem can be broken into discrete subproblems.
Why it matters: This helps you recognize when dynamic programming might be useful. - Grid cells and solution values: Describe how a dynamic programming grid represents subproblems and the values being optimized, and state that there is no single formula for every solution.
Why it matters: Thinking of each cell as a subproblem helps you design a grid suited to the problem.
Key terms: dynamic programming, constraint, discrete subproblems, grid, cells, subproblem
Concepts explained in this chapter
- dynamic programmingDynamic programming is an algorithmic technique that solves overlapping subproblems by storing and reusing their results.
- subproblemA subproblem is a smaller instance of a larger computational problem whose solution contributes to solving the larger instance.
- gridA tabular arrangement of cells that stores computed values for different knapsack capacities.
- knapsack problemThe knapsack problem is an optimization problem that selects items within a capacity constraint to maximize their combined value.
- optimal solutionAn optimal solution is a feasible solution that achieves the best possible objective value for an optimization problem.
- greedy algorithmA greedy algorithm constructs a solution by repeatedly making locally best choices without generally reconsidering earlier choices.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.