When one index can't describe where you are — a position in a maze, a pair of string prefixes, a budget with items left — the DP table grows a second axis. Same religion as Chapter 20; the recurrence just has more neighbors.
Chapter 20 taught the creed: same subproblem, same answer — so cache it. There the state was one number ("standing at stair i"), so the cache was a strip. This chapter is what happens when one number isn't enough to say where you are: the strip becomes a sheet, and three huge problem families move in — grids, string pairs, and knapsacks.
The good news: nothing conceptually new happens. You still write the choice, read the recurrence off it, and fill cells in dependency order. The table just gained an axis — and, at the end, we'll take that axis away again with the space squeeze, including the famous backwards budget loop that separates people who understand 0/1 knapsack from people who copied it.
A DP state is the minimal answer to "what do I need to know to finish from here?" In Chapter 20 that was a single index. But look at what these problems need:
Two numbers of state → a two-dimensional table. Everything else is Chapter 20 verbatim: each cell is a subproblem, the recurrence says which neighbor cells it reads, and the fill order just has to respect those arrows. The cost is honest bookkeeping: O(m·n) — every cell once, constant work per cell.
One reflex worth installing now: the table's axes are the state, and its arrows are the choice. If you can say both sentences out loud — "a cell means X", "a cell comes from its neighbors by choosing Y" — you have the whole solution; the code is transcription.
The gateway drug is Unique Paths Medium: a robot at the top-left of a grid walks only right or down; how many routes reach the bottom-right? Brute force explores a tree of moves — exponential. But ask the cell-question instead: how many ways are there to arrive HERE? You can only arrive from above or from the left, so:
dp[r][c] = dp[r-1][c] + dp[r][c-1]
Seed the start with 1, sweep row by row, read the answer in the far corner. Drop an obstacle in a cell — Unique Paths II Medium — and that cell's count is simply 0; the arithmetic downstream absorbs it. Swap + for min and add a cost per cell and you've solved Minimum Path Sum Medium without learning anything new. Grid DP is one recurrence wearing three problem titles.
Here's the move that unlocks a dozen classics: put one string on each axis. Cell (i, j) then means "the answer for the first i letters of A versus the first j of B" — every pair of prefixes is a subproblem, and the full answer sits in the bottom-right corner.
Longest Common Subsequence Medium is the flagship. The choice at (i, j) compares the two letters at the frontier:
Row 0 and column 0 are the empty-prefix base cases — all zeros, free of charge. Fill row by row, and when the table is full, walk the arrows backwards from the corner to recover the actual subsequence, not just its length. The loom below does exactly that: matches spark on the diagonal, and the traceback threads the answer out of the fabric.
Edit Distance Medium — the minimum number of insert / delete / replace operations turning string A into string B — sounds like a different universe. It's the same grid with the arrows relabeled. Cell (i, j) = cost of turning the first i letters of A into the first j of B, and the three repairs are the three neighbors:
Take the cheapest of the three. The base cases stop being zeros — turning i letters into nothing costs i deletions, so row 0 and column 0 count up 0, 1, 2, … — and everything else is LCS with min instead of max.
Third family. You have items with weights and values, a bag with a capacity, and each item exists once — take it or leave it, no halves, no repeats. Greedy by value-per-kilo fails (Chapter 19 showed you the counterexample genre), so we enumerate — cleverly. State: dp[i][w] = the best value using only the first i items with budget w. The choice at each cell is binary:
Take the max. That's the entire mechanism — and it's secretly everywhere, wearing disguises with no bags in sight. Partition Equal Subset Sum Medium asks "can this array split into two equal-sum halves?" — that's "can some subset hit exactly total/2?", a knapsack where value doesn't matter and the dp holds booleans. Target Sum Medium assigns +/− signs to hit a target — a little algebra (the plus-pile must sum to (total+target)/2) turns it into counting subsets that hit a total. Same table, three different cell types: max, boolean, count.
Stare at any recurrence in this chapter: every cell reads only from row i−1 and earlier in row i. So why store the whole sheet? Keep two rows — previous and current — and the space drops from O(m·n) to O(n). For LCS-style tables that's the whole trick, and putting the shorter string on the columns makes it O(min(m,n)).
Knapsack squeezes even harder: one row, updated in place. But now direction matters. The "take" arrow reads dp[i-1][w-wᵢ] — a cell from the previous row, to the left. If you sweep the budget left-to-right, you overwrite the left cells first, so dp[w-wᵢ] already contains this item's contribution — and the item gets taken twice, three times, as often as it fits. Sweep the budget right-to-left and every cell you read is still yesterday's row: each item counted at most once.
Here's the beautiful part: that "bug" is a feature with a name. Sweeping forwards deliberately reuses items — which is exactly the unbounded knapsack, and exactly what Chapter 20's Coin Change Medium loop was doing all along. The loop direction is the item-reuse policy: backwards = 0/1, forwards = unlimited. One character of code, two different problems.
The second axis doesn't have to be big. Sometimes it's tiny and categorical: not "budget 0…10 000" but "which of three modes am I in?" Best Time to Buy and Sell Stock with Cooldown Medium is the poster child. Chapter 6's Stock I had a one-pass greedy scan; add the rule "after selling, you must cool down a day" and the greedy story collapses — today's best move depends on yesterday's mode. So make the mode part of the state:
That's a 2-D table with a comically short second axis — n days × 3 states — filled left to right in O(n) time and, since each day reads only yesterday, O(1) space. Draw the three circles and the arrows between them before writing the recurrence; the recurrence is just the arrow list read out loud. House Robber from Chapter 20 was secretly this too: two states, "robbed" and "didn't".
Every problem in this chapter yielded to the same interrogation, and it's worth seeing the questions laid bare, because they're what you'll actually do at the whiteboard with a problem you've never seen:
Answer those four and the code writes itself — which is why Chapter 23's decision tree ends many of its branches at this chapter. It's not that 2-D DP is common; it's that once recognized, it's mechanical.
The pattern, as a whiteboard skeleton:
The flagship: Longest Common Subsequence Medium, full table first, then the two-row space squeeze from Section 6. Read the recurrence as the two sentences from Section 3 — match → diagonal + 1; mismatch → best of dropping a letter — and notice how little else there is. The squeeze version is the same arithmetic holding only what the arrows can actually reach.
In the room, write the full-table version — it's easier to trace, and tracing is scored. Mention the squeeze ("each row only reads the previous one, so this is O(min(m,n)) space if we need it") and write it only if asked. That one sentence banks the follow-up points without spending the minutes.