2-D DP & String DP (LCS, Edit Distance)

From one index to two

Every problem so far has had a single "position" you're moving through — an index into one array, a day, a capacity. 2-D DP introduces a second independent dimension, most often because you're comparing or moving through two sequences (or one grid) simultaneously. The mental model doesn't change: you still define a state, derive a transition from a brute-force recursion, and pick an iteration order that respects dependencies. You're just filling a table instead of an array.

Grid-path DP: the table is the input

The simplest 2-D shape: you're moving through an actual grid, and dp[i][j] represents the best/total result reaching cell (i, j), computed from the cells that can move into it (typically (i-1, j) and (i, j-1) for a "right or down only" grid).

The pattern generalizes immediately: swap + for min/max and you're minimizing/maximizing a path sum instead of counting paths; add obstacle checks and you're handling blocked cells. Once you see the grid as a DAG where edges only point right and down, "compute cell (i,j) after everything above and to its left" is the only iteration order that makes sense — row-major order naturally satisfies this.

Two-sequence DP: LCS as the archetype

The far more common 2-D shape in interviews doesn't involve a literal grid — it involves two strings or arrays, and dp[i][j] represents the answer for prefixes s1[:i] and s2[:j]. This is the shape behind Longest Common Subsequence, and once you internalize LCS's recurrence, Edit Distance and several other "compare two sequences" problems become variations on the same idea rather than new problems to memorize.

State: dp[i][j] = length of the longest common subsequence of the first i characters of s1 and the first j characters of s2.

Transition:

• If s1[i-1] == s2[j-1] (the characters at this position match): this character can extend a common subsequence, so dp[i][j] = 1 + dp[i-1][j-1].
• Otherwise: this pair of characters contributes nothing new, so take the best of dropping one character from either side: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Base case: dp[0][j] = dp[i][0] = 0 — an empty prefix has no common subsequence with anything. This is exactly why 2-D string DP tables are conventionally sized (len(s1)+1) x (len(s2)+1): row/column 0 represents the empty-prefix case, letting you avoid special-casing i == 0 or j == 0 inside the main loop.

Edit Distance: LCS's recurrence, one operation richer

Edit Distance (minimum operations — insert, delete, replace — to turn one string into another) uses the exact same dp[i][j]-over-two-prefixes skeleton as LCS, but the transition has three cases instead of two, because there are three edit operations instead of one "extend or drop" choice:

• If s1[i-1] == s2[j-1]: no edit needed here — dp[i][j] = dp[i-1][j-1].
• Otherwise, take the minimum of the three operations, each reducing to a smaller subproblem:
  • Replace s1[i-1] with s2[j-1]: 1 + dp[i-1][j-1]
  • Delete s1[i-1]: 1 + dp[i-1][j]
  • Insert s2[j-1] into s1: 1 + dp[i][j-1]

$$dp[i][j] = \begin{cases} dp[i-1][j-1] & s_1[i-1] = s_2[j-1] \ 1 + \min(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]) & \text{otherwise} \end{cases}$$

Notice the base cases now carry meaning: dp[i][0] = i (deleting all of s1's first i characters to match an empty s2) and dp[0][j] = j (inserting all of s2's first j characters) — not zero. This is a common place candidates copy the LCS base case (0) out of habit and get a wrong answer despite an otherwise-correct transition.

The general technique: what changes, what doesn't

	LCS	Edit Distance	Grid Path DP
State meaning	Best result over prefixes s1[:i], s2[:j]	Best result over prefixes s1[:i], s2[:j]	Best result reaching cell (i,j)
"Match" case	Extend by 1: 1 + dp[i-1][j-1]	No-op: dp[i-1][j-1]	N/A — no character matching
"No match" case	Drop from either side, take max	Try all 3 edits, take min	Combine from the 2 predecessor cells
Base case (row/col 0)	0 (no subsequence with nothing)	i or j (all inserts/deletes)	1 or grid value (depends on problem)
Iteration order	Increasing i, then increasing j	Same	Row-major (increasing i, then j)

The takeaway: the skeleton — two indices, a table, dependencies on (i-1,j), (i,j-1), (i-1,j-1) — is reusable across nearly all two-string problems. What changes from problem to problem is (a) what each cell means (your one-sentence state definition) and (b) what the base cases represent, which follows directly from that meaning. Derive the meaning first, and the recurrence and base cases fall out almost mechanically.

Reconstructing the actual answer, not just its length/count

Many 2-D DP problems ask for more than a number — the actual longest common subsequence itself, or the actual sequence of edits. The table already contains everything you need: backtrack from dp[m][n] toward dp[0][0], re-deriving at each cell which transition case produced its value.

This backtracking step is O(m + n) — cheap relative to the O(m × n) table build — but it requires the full table, which is exactly why the space-optimized "two rows" trick (below) doesn't work if reconstruction is required: you've thrown away the rows you'd need to backtrack through.

Space optimization

Since row i's values only depend on row i-1 (and the current row so far), you can drop the table to two 1-D rows (or even one row updated carefully), reducing space from O(m × n) to O(n). This is a standard follow-up question — but flag explicitly that it sacrifices the ability to reconstruct the answer, since the trade-off is exactly analogous to the knapsack space-optimization trade-off from the previous subtopic.

Complexity

For two sequences of length m and n: O(m × n) time and space for the full table, O(n) space with row-rolling. Grid-path DP over an m × n grid is likewise O(m × n) time and space. Reconstruction adds O(m + n), negligible relative to table construction.

Common pitfalls

• Wrong base case values. LCS bases are 0; Edit Distance bases are i/j — copying one pattern into the other's problem is a frequent, hard-to-spot bug.
• Off-by-one between string index and DP index. dp[i][j] refers to the first i/j characters, so the character being compared is s[i-1]/s[j-1], not s[i]/s[j]. This single shift is the most common source of index errors in this subtopic.
• Iterating in the wrong order and reading a cell that hasn't been computed yet — for these two-prefix problems this almost never happens if you go row-major, but it becomes a real risk once you generalize to Interval DP next, where the "natural" row-major order is actually wrong.
• Confusing "subsequence" with "substring." A subsequence need not be contiguous; a substring must be. Using the LCS recurrence when the problem actually wants a common substring (a different, simpler DP where a mismatch resets the count to 0 rather than falling back to a max) gives a wrong answer that can still look plausible on small test cases.
• Assuming reconstruction is "free." It requires keeping the full 2-D table in memory — state that trade-off explicitly if you've already offered the space-optimized version and the interviewer then asks for the actual reconstructed answer.