Algorithms from zero
Two-dimensional DP: grid paths, LCS, edit distance
The one-dimensional DPs you have seen so far had a single moving part: the state was one number, like dp[i], and you filled a single row of values. But a huge family of problems needs two indices at once. How many ways are there to walk from the top-left of a grid to the bottom-right? How similar are two strings? How few edits turn kitten into sitting? Each of these has a subproblem described by two positions—a row and a column, or an index into each string. The state becomes dp[i][j], and the cache becomes a 2D table. The mechanism is identical to 1D DP—define the state, write the recurrence, fix the base cases, fill in order, read the answer—just over a grid instead of a line.
After this lesson you can recognize when a problem needs a two-dimensional state dp[i][j] and set up the matching 2D table. You can define the state precisely (what dp[i][j] means), write the recurrence from the cell’s neighbors, fix the base row and base column, choose a fill order so every cell’s dependencies are already computed, and read the answer at the bottom-right. You can work three classics from memory: unique grid paths (dp[i][j] = dp[i-1][j] + dp[i][j-1]), longest common subsequence (dp[i-1][j-1]+1 on a match, else max(dp[i-1][j], dp[i][j-1])), and edit distance (insert, delete, or replace). You know the complexity is O(m·n) time and O(m·n) space, and you can shrink the space to O(min(m,n)) with a rolling array because each row depends only on the row above. Next unit moves beyond grids to more general DP shapes.
When the state needs two indices
In two-dimensional DP, a subproblem cannot be described by one number—it needs two. The state is dp[i][j], where i and j are two independent positions: a row and a column in a grid, or an index into each of two strings. Because the state is a pair, the cache is a 2D table (an array of arrays), and you fill it in two nested loops instead of one.
Everything else is the same five-step recipe as 1D DP:
- Define the state. Say in one sentence what
dp[i][j]means. This is the hardest and most important step—get it right and the recurrence falls out. - Write the recurrence. Express
dp[i][j]in terms of cells you have already filled (usuallydp[i-1][j],dp[i][j-1],dp[i-1][j-1]). - Set the base cases. Fill the first row and first column directly—they have no “previous” cell to lean on.
- Choose a fill order. Loop so that every cell’s dependencies are computed before it. Top-to-bottom, left-to-right works whenever a cell depends only on cells above and to the left.
- Read the answer. It is almost always the bottom-right cell,
dp[m][n]—the state for the full problem.
Classic 1: unique paths in a grid
A robot starts at the top-left of an m × n grid and can move only right or down. How many distinct paths reach the bottom-right? Define dp[i][j] = number of paths from the start to cell (i, j). To reach (i, j) your last move came either from above (i-1, j) or from the left (i, j-1), so:
dp[i][j] = dp[i-1][j] + dp[i][j-1]Base: the entire first row and first column are 1 (only one straight-line way to reach any edge cell). The answer is dp[m-1][n-1]. A 3 × 3 grid:
c0 c1 c2
r0 1 1 1
r1 1 2 3
r2 1 3 6 <- 6 paths to bottom-rightClassic 2: longest common subsequence (LCS)
A subsequence keeps characters in order but may skip some (no rearranging). LCS finds the longest sequence appearing in both strings. Define dp[i][j] = length of the LCS of the first i characters of A and the first j characters of B. Compare the last characters of each prefix:
if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 // match: extend the diagonal
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // mismatch: drop one charBase: row 0 and column 0 are all 0 (the LCS with an empty string is empty). The answer is dp[m][n]. Filled table for A = ABCBDAB, B = BDCAB:
'' B D C A B
'' 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4 <- LCS length 4 (e.g. "BCAB" or "BDAB")Notice the +1 reads the diagonal dp[i-1][j-1], while the max reads the cell above and the cell left. Those three neighbors are the heart of every string DP.
Classic 3: edit distance (Levenshtein)
Edit distance is the minimum number of single-character insert, delete, or replace operations to turn string A into string B. Define dp[i][j] = edit distance between the first i chars of A and the first j chars of B. If the last characters match, no new edit is needed; otherwise take the cheapest of the three operations and add one:
if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(
dp[i-1][j], // delete A[i-1]
dp[i][j-1], // insert B[j-1]
dp[i-1][j-1] ) // replace A[i-1] with B[j-1]Base cases carry real meaning here: dp[i][0] = i (delete all i chars to reach the empty string) and dp[0][j] = j (insert all j chars from nothing). The answer is dp[m][n]. kitten → sitting is 3 (replace k→s, replace e→i, insert g).
The shared shape
All three define dp[i][j], fill a base row and base column, then fill the interior from already-computed neighbors, and read the answer at the bottom-right. Unique paths adds two neighbors; LCS and edit distance combine the diagonal plus the two orthogonal neighbors. Once you see this pattern, most grid-and-string DP problems look the same.
Longest common subsequence, bottom-up
The state is the pair (i, j), so the cache is a (m+1) × (n+1) table. The extra row and column hold the empty-prefix base case (all zeros), which is why indices into the strings are A[i-1] and B[j-1].
1
function lcs(a, b) {
2
const m = a.length, n = b.length;
3
// (m+1) x (n+1) table; row 0 and col 0 are the empty-prefix base (all 0)
4
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
5
6
for (let i = 1; i <= m; i++) {
7
for (let j = 1; j <= n; j++) {
8
if (a[i - 1] === b[j - 1]) {
9
dp[i][j] = dp[i - 1][j - 1] + 1; // match: extend the diagonal
10
} else {
11
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // mismatch: drop one char
12
}
13
}
14
}
15
return dp[m][n]; // answer is the bottom-right cell
16
}
- L2 m and n are the lengths of the two strings.
- L4 Allocate a 2D table sized (m+1) by (n+1), filled with zeros.
- L6 Outer loop walks rows i = 1..m; row 0 stays the all-zero base case.
- L7 Inner loop walks columns j = 1..n; column 0 stays the all-zero base case.
- L8 Compare last chars of the two prefixes: A[i-1] and B[j-1].
- L9 Match: the LCS grows by one beyond the diagonal cell dp[i-1][j-1].
- L11 Mismatch: best of dropping A's last char (above) or B's last char (left).
- L15 The full-problem state dp[m][n] is the LCS length.
Key point: the table is one size bigger than the strings
The table has m+1 rows and n+1 columns, not m and n. Index 0 of each axis is the empty prefix, whose LCS is 0. That extra border is what lets the recurrence read dp[i-1][j-1] even when i or j is 1 without falling off the table.
Running it
Edit distance, same shape with three options
Edit distance reuses the exact table structure—only the recurrence and the base row/column change. Here the base cases are non-zero: turning a length-i prefix into the empty string costs i deletions, so dp[i][0] = i, and symmetrically dp[0][j] = j.
Let us fill the LCS table for the short pair A = "AB", B = "AC". The table is 3 × 3 (one extra row and column for the empty prefix). Row 0 and column 0 start at 0. We fill row by row, left to right, watching each interior cell read its three neighbors (above, left, diagonal).
1
for i in 1..m:
2
for j in 1..n:
3
if A[i-1] == B[j-1]:
4
dp[i][j] = dp[i-1][j-1] + 1
5
else:
6
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Time: O(m·n)
There are (m+1) × (n+1) cells in the table, which is O(m·n). Each cell does O(1) work: a comparison and a max or min over a fixed number of neighbors. So the total time is
total time = (number of states) x (work per state) = O(m*n) x O(1) = O(m*n)For two strings of length 1000 that is about a million cell computations—fast. This is the same complexity rule as 1D DP (distinct states times work per state); the only change is that the number of states is now a product of two dimensions instead of one.
Space: O(m·n), shrinkable to O(min(m, n))
The full table stores every cell, so the straightforward version uses O(m·n) space. But look at the recurrences: dp[i][j] reads only from row i and row i-1. It never touches row i-2 or earlier. So you only need to keep two rows at a time—the current one and the previous one—and overwrite as you go. This is the rolling array trick:
full table: O(m*n) space (keep every row)
two rows: O(n) space (keep current + previous row)
one row: O(n) space (overwrite carefully, saving the diagonal in a temp)To make the kept row the smaller dimension, loop with the shorter string along the columns; then the space is O(min(m, n)). The catch: rolling rows give you only the final number. If you also need to reconstruct the actual subsequence or edit script, you must keep the full O(m·n) table to walk back through it.
time space gives the path back?
full 2D table O(m*n) O(m*n) yes
rolling rows O(m*n) O(min(m,n)) no (number only)The 1D-to-2D jump
The mental model does not change from 1D: count the distinct states, multiply by the per-state work. A 1D DP over n had n states and O(n) time. A 2D DP over an m × n grid has m·n states and O(m·n) time. If a future problem needed three indices, the table would be 3D and the time O(m·n·p)—same rule, more dimensions.
In unique-paths grid counting, what is the recurrence for dp[i][j] (paths to cell (i,j)), given moves can only be right or down?
For longest common subsequence, what does dp[i][j] equal when the last characters match, i.e. A[i-1] == B[j-1]?
In edit distance, why are the base cases dp[i][0] = i and dp[0][j] = j (rather than all zeros like LCS)?
After filling a 2D DP table top-to-bottom and left-to-right, where do you read the answer to the full problem?
Why can 2D DP space often be reduced from O(m*n) to O(min(m,n))?
Computing edit distance between two strings of length 200 and 300 fills a (200+1) x (300+1) table. How many cells is that?
Why this works
Why the extra row and column? The table is (m+1) × (n+1), not m × n. The index-0 row and column represent an empty prefix of each string. Without them, the recurrence dp[i-1][j-1] would fall off the table whenever i or j equals 1. The border encodes the smallest base case (LCS with empty = 0; edit distance with empty = the other length) and gives every interior cell a valid neighbor to read. This is why string indices appear as A[i-1] and B[j-1]: table row i corresponds to string character i-1.
Common mistake
Wrong fill order, or reading the wrong neighbor. A 2D recurrence is only correct if every cell’s dependencies are already filled when you reach it. dp[i][j] depending on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] is safe with top-to-bottom, left-to-right loops — but if a recurrence ever read dp[i+1][j] you would need the opposite direction. A second common slip is confusing the three neighbors: the match case reads the diagonal dp[i-1][j-1], the mismatch case reads above and left. Swapping them silently produces wrong answers that still “look” plausible on small inputs.
Edge cases
Empty strings and identical strings. If either string is empty, the answer is immediate from the base cases: LCS is 0, and edit distance is the length of the non-empty string. If the strings are identical, LCS equals their length and edit distance is 0. These extremes are exactly what the base row and column encode, so a correct table handles them with no special-casing. Always sanity-check your code on an empty input and on two equal inputs — they catch most off-by-one and base-case bugs.
More practice
The 2D DP recipe. (1) Write one sentence defining dp[i][j]. (2) From that definition, derive the recurrence by asking “what choices lead into state (i,j)?” — usually the cells above, left, and diagonal. (3) Fill the base row and base column directly from the definition. (4) Loop top-to-bottom, left-to-right so dependencies are ready. (5) Read dp[m][n]. Then optimize: if you only need the final number and not the reconstructed path, collapse to a rolling array for O(min(m,n)) space. Practice by hand-filling the unique-paths and edit-distance tables for tiny inputs before trusting the code.
Explain how two-dimensional DP works: the state, why the table has an extra row and column, the LCS and edit-distance recurrences, where the answer lives, and the time and space complexity.
Two-dimensional DP is for problems whose subproblem needs two indices: the state is dp[i][j] and the cache is a 2D table.
The five-step recipe (same as 1D, over a grid): define what dp[i][j] means; write the recurrence from already-filled neighbors (above dp[i-1][j], left dp[i][j-1], diagonal dp[i-1][j-1]); fill the base row and base column; loop top-to-bottom, left-to-right; read the answer at the bottom-right dp[m][n].
Three classics:
- Unique paths:
dp[i][j] = dp[i-1][j] + dp[i][j-1], base row and column all 1. - LCS:
dp[i-1][j-1]+1on a match, elsemax(dp[i-1][j], dp[i][j-1]), base border all 0. - Edit distance:
dp[i-1][j-1]on a match, else1 + min(delete, insert, replace), basedp[i][0]=i,dp[0][j]=j.
The extra row and column hold the empty-prefix base case so the border recurrence has a valid neighbor; string char i sits at table row i+1.
Complexity: O(m·n) time (states times O(1) work). Space is O(m·n), shrinkable to O(min(m,n)) with a rolling array because each cell depends only on the current and previous row — but keep the full table if you need to reconstruct the actual path.
Next unit moves past grids and strings to more general DP shapes built on this same state-recurrence-base-fill-read discipline.