4.24.0 — 2-D Dynamic Programming: The Pattern

Recognition cue. The state needs two numbers. Almost always one of these three shapes:

shape	the two dimensions	example
two sequences	a position in each	LCS, Edit Distance
a grid	row and column	Unique Paths
a position plus something else	index and a budget, a count, or a state	knapsack, stock with cooldown

"Two strings" is the strongest cue in the whole chapter. The moment a problem gives you two sequences, draw a grid with one axis per string and ask what happens at the last character of each.

The two questions

1. What are the two cases at each cell? For two-sequence problems it is nearly always the characters match or they do not. Everything else follows.

2. What order fills the table? List what the recurrence reads. If it reads a smaller row and a smaller column, fill top to bottom, left to right. If it reads shorter ranges, fill by increasing length. Half of all 2-D DP bugs are reading a cell that has not been filled yet.

The two-sequence template

dp = [[0] * (n + 1) for _ in range(m + 1)]      # (m+1) × (n+1), NOT m × n

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if a[i-1] == b[j-1]:
            dp[i][j] = ...                       # the match case
        else:
            dp[i][j] = ...                       # the mismatch case

The +1 sizing and the −1 offsets go together. Row i means "the first i characters", so row 0 is the empty prefix and gives the base row for free. Sizing the table m × n forces special cases for the first row and column, and that is where the errors come from.

Only the two cases change between problems:

problem	match	mismatch
LCS	1 + dp[i-1][j-1]	max(dp[i-1][j], dp[i][j-1])
Edit Distance	dp[i-1][j-1]	1 + min(three)
Distinct Subsequences	dp[i-1][j-1] + dp[i-1][j]	dp[i-1][j]
Longest Common Substring	1 + dp[i-1][j-1]	0 — must be contiguous

Interval DP: the other fill order

When the state is a range rather than two independent positions, the recurrence reads shorter ranges, so the loop is over length:

for length in range(2, n):
    for left in range(n - length):
        right = left + length
        for i in range(left + 1, right):        # the split point
            dp[left][right] = best(dp[left][i], dp[i][right], ...)

O(n^2) states and O(n) transitions gives O(n^3) — and n ≤ 300 in the constraints is the setter telling you that is the budget.

For interval problems, ask what happens LAST in the range, not first. Choosing the last event is what makes the two sides independent. That is the whole trick of 4.24.10 Burst Balloons.

Space optimisation, and its cost

If the recurrence reads only the previous row, two rows suffice — and often one, with the right loop direction:

• Reading a smaller column from the previous row (dp[j-1] meaning the row above) → iterate backwards.
• Reading a smaller column from the current row (dp[j-1] meaning this row) → iterate forwards.

The cost is always the same: you can no longer reconstruct the answer, only its value. Keep the full table whenever the problem asks which rather than how many or how much.

The eleven problems

#	Problem	The one insight
4.24.1	Unique Paths ★	Arrive from the left or from above
4.24.2	Longest Common Subsequence ★	The two-string grid template
4.24.3	Stock with Cooldown	The second dimension is a state, not a position
4.24.4	Coin Change II	Coins outside = combinations; inside = permutations
4.24.5	Target Sum	Algebra first: it reduces to a subset count
4.24.6	Interleaving String	s3's position is i + j, so no third dimension
4.24.7	Longest Increasing Path	Strictly increasing = a DAG, so no visited set
4.24.8	Distinct Subsequences	A match is optional, so the counts add
4.24.9	Edit Distance ★	Three operations = three neighbours
4.24.10	Burst Balloons	Choose which balloon bursts last
4.24.11	Regular Expression Matching	Read the pattern in x* pairs

★ marks the Blind 75 subset.

The traps on this pattern

Sizing the table m × n instead of (m+1) × (n+1). You lose the free base row and column.

Filling in the wrong order. List what the recurrence reads before writing the loops.

Rolling the array in the wrong direction. Backwards when reading a smaller column from the previous row; forwards when reading the current row.

Assuming a third dimension. Interleaving String looks 3-D and is not.

Treating * as an independent character in regex matching. It attaches to what precedes it.

What the interviewer will push on

"Why two dimensions?" Name what each axis is, in words.

"What are the two cases?" Match and mismatch, for every two-sequence problem.

"What order do you fill the table, and why?" The recurrence's dependencies.

"Can you reduce the space?" Two rows or one, with the direction justified — and say that reconstruction is lost.

"How would you recover the actual answer?" Keep the table and walk backwards, checking which predecessor produced each value.

One thing to volunteer: say the state definition, the two cases and the fill order out loud before writing anything. On 4.24.10 that habit is the difference between solving it and not.

Recall

• Two sequences → a grid with one axis each. That is the strongest recognition cue in the chapter.
• Size the table (m+1) × (n+1) so the empty prefixes give the base row and column for free.
• Every two-sequence recurrence is the characters match or they do not. Only those two lines change between problems.
• Fill order comes from what the recurrence reads. Smaller row and column → top-left to bottom-right. Shorter ranges → loop over length (interval DP, O(n^3)).
• For interval problems, ask what happens last, not first — that is what makes the two sides independent.
• Rolling direction: backwards when dp[j-1] must mean the previous row, forwards when it must mean the current one.
• Space optimisation costs reconstruction. Keep the table when the question asks which.
• The second dimension is not always a position — it can be a state (holding / sold / resting) or a budget.

Next: 4.24.1 Unique Paths — the simplest grid, and the place to build the fill-order habit.