Dynamic Programming II: Two Dimensions

Compare two strings — say, two versions of a document — and ask: what's the longest sequence of characters they share, in order but not necessarily contiguous? That's longest common subsequence (LCS), and it's the canonical two-sequence problem.

Try to write a 1-D state sentence for it and you'll fail: "best answer for the first i characters" — of which string? Progress through a and progress through b are independent. The fix is to track both:

dp[i][j] = length of the LCS of the first i characters of a and the first j characters of b.

Same discipline as 1-D — one precise English sentence before any code — just with two indices. The recurrence falls out of the last-decision question. Stand at (i, j) and look at the last characters, a[i-1] and b[j-1]:

• They match. Then they end the common subsequence together: dp[i][j] = dp[i-1][j-1] + 1 — one diagonal step back, plus one.
• They don't. At least one of them is dead weight. Drop whichever and keep the better result: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Base cases: dp[0][j] = dp[i][0] = 0 — an empty string shares nothing with anything. Note the off-by-one convention: dp is (n+1) × (m+1) and dp[i][j] covers prefixes of length i and j. That extra zero row and column is what makes the base cases free instead of fiddly.

Do this once slowly and 2-D DP stops being scary. Take a = "ace", b = "abcde". Rows are prefixes of a, columns are prefixes of b, and row 0 / column 0 are the all-zero borders:

          ""   a    b    c    d    e
     ""    0   0    0    0    0    0
     a     0   1    1    1    1    1
     c     0   1    1    2    2    2
     e     0   1    1    2    2    3

Trace a few cells:

• dp[1][1] ("a" vs "a"): characters match → diagonal dp[0][0] + 1 = 1.
• dp[1][2] ("a" vs "ab"): a != b → max(dp[0][2], dp[1][1]) = max(0, 1) = 1. The b bought us nothing.
• dp[2][3] ("ac" vs "abc"): c == c → diagonal dp[1][2] + 1 = 2.
• dp[3][5] ("ace" vs "abcde"): e == e → diagonal dp[2][4] + 1 = 3. That's the answer, sitting in the bottom-right corner as always.

The code is a transcription of the walk:

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Time and space are both O(n·m) — number of states times O(1) work per state, exactly the 1-D formula with one more dimension. Fill order: row by row, left to right, because each cell reads up, left, and up-left — all already filled.

Sometimes the two dimensions aren't two sequences — they're an actual grid. A delivery robot starts at the top-left of an m × n warehouse floor and can only move right or down. How many routes reach the bottom-right?

The state sentence writes itself:

dp[r][c] = number of ways to reach cell (r, c).

Last decision: the final move into (r, c) came from above or from the left, so

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

with the whole first row and first column equal to 1 (only one way to slide along an edge). It's climbing stairs in two dimensions — the + says counting, just like stairs; swap it for min and add cell costs and you've got minimum-path-sum; mark some cells as blocked and you zero them out. One picture, a family of problems.

The grid view is worth keeping in your head even for sequence problems, because every 2-D DP is a grid walk: LCS is a walk through the (i, j) grid where matches move diagonally and mismatches move right or down. If you can draw the grid and the arrows into a cell, you can write the recurrence.

The third source of a second dimension: one index walks your choices, the other tracks a budget. Classic instance — count the ways to make an amount from coin denominations, each usable unlimited times (coin change II).

The trap: a 1-D "ways to make amount a" state counts orderings — it sees 2+5 and 5+2 as different. To count combinations, the state must remember which coins are still on the table:

dp[i][a] = number of ways to make amount a using only the first i coin types.

Last decision at (i, a): did the combination use coin i at all?

• No → dp[i-1][a]: same amount, one fewer coin type.
• Yes, at least once → dp[i][a - coins[i-1]]: spend one copy, and stay on row i because the coin is reusable.

dp[i][a] = dp[i - 1][a] + dp[i][a - coin]   # second term only if a >= coin

with dp[i][0] = 1 for all i (one way to make zero: take nothing). Staying on the same row for the "use it again" branch is the unbounded-knapsack signature; the 0/1 knapsack variant points that term at row i-1 instead, because each item can be used once. That single index — which row does the "take it" arrow come from — is the entire difference between the two knapsacks. Say it out loud in an interview and you'll sound like you've seen everything.

Here's the meta-skill this lesson is really about. For any 2-D DP, draw one cell and ask: which neighboring cells feed into me, and what does each arrow mean?

Now reread the problems you know: LCS is diagonal-on-match, max-of-up-and-left otherwise. Unique paths is up + left. Edit distance is all three arrows with min and a cost. Coin change II is up + a left-jump of length coin on the same row. New problem, same routine: write the state sentence, draw a cell, name the arrows. The recurrence is the arrows; the code is the recurrence plus a fill order that respects them.

And the checklist from 1-D carries over wholesale: pin base cases (usually row 0 and column 0), pick a fill order where every arrow points at an already-filled cell, locate the answer (almost always the far corner — unless the state is "ending at", in which case scan for the max), and sanity-check a 3×3 table by hand before trusting any code.

Look back at every recurrence above: dp[i][...] reads only row i and row i-1. Never row i-2. So why store n+1 rows?

Keep two rows and swap:

prev = [0] * (m + 1)
for i in range(1, n + 1):
    cur = [0] * (m + 1)
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            cur[j] = prev[j - 1] + 1
        else:
            cur[j] = max(prev[j], cur[j - 1])
    prev = cur
return prev[m]

O(n·m) time still, but O(m) space — the same rolling-window squeeze as 1-D stairs, one dimension up. Often you can go further and use a single row updated in place; the catch is direction. cur[j - 1] (left) is the current row, fine; but if the recurrence needs the old dp[i-1][j-1] you must stash it in a temp before overwriting, or iterate j in the order that preserves what you still need. Unbounded knapsack wants left-to-right (reuse allowed, reading the new row is correct); 0/1 knapsack wants right-to-left (so the "take it" arrow still reads the previous row). Getting that direction wrong is the classic one-row bug — and explaining why the direction matters is the classic way to ace the follow-up.

One caveat before you compress: if the interviewer asks you to reconstruct the actual subsequence or path, you need the full table to walk backwards through. Optimize space only after confirming they just want the number.