2D Dynamic Programming & Grids

The 10-second versionCopy Anchor Link

Sometimes a subproblem genuinely depends on two things at once: where you are in the first string and where you are in the second, or which row and which column of a grid. When that happens you make the state an ordered pair and store the answers in a two-index table, dp[i][j]. Each cell is filled from a small, fixed set of neighbors — usually the cell above, the cell to the left, and the diagonal — and the answer you want ends up in a corner. Nearly every "compare two sequences" and "walk a grid" problem is this one shape wearing different clothes.

Why this existedCopy Anchor Link

The problem goes back to the mid-1960s and a very practical question: how do you make a machine decide that two strings are almost the same? Not equal or not — how far apart.

In 1965 the Soviet mathematician Vladimir Levenshtein defined exactly that: the minimum number of single-character edits — insert one, delete one, or swap one for another — needed to turn one string into another. He wasn't chasing spell-check; he was working in coding theory, on how to describe the difference between binary messages so that errors could be detected and corrected. But the distance he defined turned out to be the thing that powers the fuzzy matching you use every day.

The obvious approach — try every way of lining the two strings up and count the cheapest — blows up, because the number of alignments is exponential in the length. What was needed was a way to reuse work: the cost of aligning the first ten characters against the first twelve shares almost all of its structure with the cost of aligning nine against eleven.

• 1965 — Levenshtein defines the edit distance and an efficient algorithm for it.
• 1970 — Needleman & Wunsch align biological sequences (proteins) with essentially the same grid, igniting computational biology.
• 1974 — Wagner & Fischer give the clean general dynamic-programming formulation for arbitrary edit costs — the version in every textbook.
• Today — a git diff, a spell-checker, a DNA aligner, and your phone's autocorrect all fill this same table.

Why it mattered then: a machine that could say "these two things are close" could correct transmission errors without resending the whole message, and — a decade later — could line up genes. The table was the first tool that made "how different" a computable number instead of a vibe.

Inside the inventor's headCopy Anchor Link

Here's how you discover the grid without being told about it. Ask the natural recursive question: to compare the prefixes ending at position i of A and position j of B, look only at the last characters.

• If A[i-1] equals B[j-1], those two match for free — the cost is just whatever it costs to compare the shorter prefixes i-1 and j-1.
• If they differ, the very last edit must be one of three moves: delete the extra character of A (then compare i-1 with j), insert a character into A to match B's last one (then compare i with j-1), or substitute (then compare i-1 with j-1, plus one for the swap).

That's a decision tree:

The first attempt is to just recurse on this tree. It's correct — and catastrophically slow, because the same (i, j) pair is recomputed over and over:

function edit(a, i, b, j) {  if (i === 0) return j;                       // A empty: insert all of B  if (j === 0) return i;                       // B empty: delete all of A  if (a[i - 1] === b[j - 1]) return edit(a, i - 1, b, j - 1);  return 1 + Math.min(edit(a, i - 1, b, j),    // delete                      edit(a, i, b, j - 1),    // insert                      edit(a, i - 1, b, j - 1)); // substitute}

For a 20-character pair, the branch (i-1, j-1) alone gets recomputed millions of times. The fix is the move you met in Dynamic Programming Foundations — memoize. Once you write down "the answer for (i, j)", you never compute it twice. And the moment you memoize a two-argument function, you're not really writing a recursion anymore; you're filling a table. The i index is a row, the j index is a column. That's the whole pivot.

The final approachCopy Anchor Link

The table and the recurrenceCopy Anchor Link

Define dp[i][j] as the edit distance between the first i characters of A and the first j characters of B. The recurrence falls straight out of the decision tree:

dp[i][j] = dp[i-1][j-1]                                     if A[i-1] == B[j-1]
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])    otherwise

with the base cases dp[i][0] = i (delete all of A's prefix) and dp[0][j] = j (insert all of B's prefix). Every cell reads only three neighbors — up, left, and up-left:

So you can fill the table row by row, top to bottom and left to right, and every neighbor is already waiting for you:

The invariantCopy Anchor Link

Before you fill cell (i, j), dp[i][j-1] already holds the distance between A's first i characters and B's first j-1, dp[i-1][j] holds the analogous distance one row up, and dp[i-1][j-1] the diagonal. The recurrence combines exactly the three possible "last edits", so the value written is the true minimum cost. By induction down the rows, the corner holds the answer. The second invariant is about order: because every dependency points strictly up, left, or up-left, any order that visits cells before their right/down neighbours works — and the plain nested i then j loop is the simplest such order.

A worked trace: cat into cutCopy Anchor Link

The answer is obviously 1 — swap the a for a u — but let's make the table earn it. Rows index A = "cat", columns index B = "cut". Fill the bases, then the body:

Read the corner: dp[3][3] = 1. To see where a mismatch cell comes from, take (2, 1): A[1] = 'a' versus B[0] = 'c' differ, so dp[2][1] = 1 + min(dp[1][1], dp[2][0], dp[1][0]) = 1 + min(0, 2, 1) = 1. Every match cell copies its diagonal; every mismatch cell is one plus the cheapest of its three neighbours. The final 1 is the single substitution.

Here is that recurrence as real code — the full two-dimensional edit distance:

function editDistance(a, b) {  const n = a.length, m = b.length;  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));  for (let i = 0; i <= n; i++) dp[i][0] = i;     // base column  for (let j = 0; j <= m; j++) dp[0][j] = j;     // base row  for (let i = 1; i <= n; i++)    for (let j = 1; j <= m; j++)      dp[i][j] = a[i - 1] === b[j - 1]        ? dp[i - 1][j - 1]        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);  return dp[n][m];}

The same shape on a gridCopy Anchor Link

Swap "two strings" for "a grid of numbers" and nothing really changes. Take unique paths: how many ways are there from the top-left corner to the bottom-right, moving only right or down? The state is the cell (i, j), and the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] — the number of ways into a cell is the sum of the ways into the cell above and the cell to the left. For minimum path sum, you take the cheaper of the two instead of adding: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Same neighbours, same fill order, a different combiner. The little 3×3 unique-paths table fills like this:

Rolling the table down to one rowCopy Anchor Link

Watch exactly what the recurrence reads: dp[i][j] needs dp[i-1][j] (the row above, same column), dp[i][j-1] (this row, previous column), and dp[i-1][j-1] (the diagonal). It never looks further back than the previous row. So the whole n × m table is overkill — one row is enough. Keep an array dp[0..m], walk the rows, and overwrite in place: by the time you write dp[j] you've already consumed the old (previous-row) value that was sitting there, and dp[j-1] already holds the current row. Memory drops from O(n·m) to O(m).

function minPathSum(grid) {  const cols = grid[0].length;  const dp = new Array(cols);  dp[0] = grid[0][0];  for (let j = 1; j < cols; j++) dp[j] = dp[j - 1] + grid[0][j];  for (let i = 1; i < grid.length; i++) {    dp[0] += grid[i][0];                         // only one way in: from above    for (let j = 1; j < cols; j++)      dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);  }  return dp[cols - 1];}

ComplexityCopy Anchor Link

Every cell is filled exactly once and does constant work, so best, average and worst coincide — there's no data-dependent shortcut in the plain recurrence. The only lever is memory, and rolling the previous row is how you pull it.

Where you meet it todayCopy Anchor Link

• Version control. git diff and every "changes between these two texts" view are LCS/edit-distance machines underneath — that's why a one-line edit shows as one changed line, not a rewritten paragraph.
• Spell-check and autocorrect. "Did you mean sitting?" is a nearest-neighbour search under edit distance: find the dictionary word with the smallest table value.
• Bioinformatics. Needleman–Wunsch (global) and Smith–Waterman (local) are the same grid with different base cases; they align DNA and protein sequences.
• Images and OCR. Seam carving finds the lowest-energy path through a pixel grid with a min-path-sum DP; handwriting and speech recognisers score candidate transcripts the same way.

The longest-common-subsequence table is the cleanest everyday instance, and it's one line of difference from edit distance — same shape, no substitution move:

function lcs(a, b) {  const dp = Array.from({ length: a.length + 1 },                        () => new Array(b.length + 1).fill(0));  for (let i = 1; i <= a.length; i++)    for (let j = 1; j <= b.length; j++)      dp[i][j] = a[i - 1] === b[j - 1]        ? dp[i - 1][j - 1] + 1        : Math.max(dp[i - 1][j], dp[i][j - 1]);  return dp[a.length][b.length];}

RecapCopy Anchor Link

• When a subproblem depends on two positions, the state is the pair and the storage is a table: dp[i][j].
• The recurrence is read off the three neighbours — up, left, and diagonal — so you can fill the table row by row and the answer lands in the corner.
• Compare-two-sequences (edit distance, LCS) and walk-a-grid (unique paths, min path sum) are the same shape with different combiners.
• If a cell only needs the previous row, roll the table to one dimension and save the O(n·m) memory.

Next up: The Knapsack Family — where the state becomes a single capacity instead of a pair of positions.