2D DP — Section 12: Dynamic Programming

2D DP problems track a state indexed by two parameters — often two positions in two strings/arrays, or row/column in a grid. The recurrence builds a 2D table; each cell depends on its neighbors.

Longest common subsequence (LCS)

Given strings $s$ and $t$ , find the longest sequence of characters appearing in both in the same order (but not necessarily contiguous). State: $f(i, j)$ = LCS of $s[0..i)$ and $t[0..j)$ .

f(i, j) = \begin{cases} f(i - 1, j - 1) + 1 & \text{if } s[i-1] = t[j-1] \\ \max(f(i - 1, j), f(i, j - 1)) & \text{otherwise} \end{cases}

$O(mn)$ time, $O(mn)$ space. Reduce to $O(\min(m, n))$ space by keeping only the last row.

Edit distance

Minimum number of insertions, deletions, and substitutions to turn $s$ into $t$ . State: $f(i, j)$ = edit distance from $s[0..i)$ to $t[0..j)$ .

f(i, j) = \begin{cases} f(i - 1, j - 1) & \text{if } s[i-1] = t[j-1] \\ 1 + \min(f(i - 1, j - 1), f(i - 1, j), f(i, j - 1)) & \text{otherwise} \end{cases}

The three options correspond to substitute, delete from $s$ , insert into $s$ . $O(mn)$ time and space.

Grid pathfinding (unique paths)

Count paths from top-left to bottom-right in an $m \times n$ grid where you can only move right or down. $f(i, j) = f(i - 1, j) + f(i, j - 1)$ with $f(0, 0) = 1$ . $O(mn)$ time and space — or $O(n)$ space with row-by-row update.

Why 2D and not 3D

You CAN have 3D DPs (and 4D and higher). They show up but are rarer. Each extra dimension multiplies state count and complicates the recurrence. Whenever you can compress a dimension (the recurrence only depends on the last row, etc.), do so.

Recognition

Two strings or two arrays, asking for some optimal alignment, common substructure, or count of paths — almost always 2D DP.