DP — 2-D & grids
📖 Walk me through it — plain English
What this is. "Dynamic programming" (DP) means solving a big problem by filling in a table of answers to smaller versions of the same problem, where each entry is built from entries you already filled. In 2-D DP the table is a grid: the answer to one cell depends on two things changing at once — usually how much of string A you've handled and how much of string B you've handled. We write that cell as dp[i][j], read "dp at row i, column j". The anchor problem here is Edit Distance: the fewest single-character edits (insert a letter, delete a letter, or replace one letter with another) to turn string A into string B. dp[i][j] means "cheapest way to make the first i letters of A look like the first j letters of B." A "prefix" is just the front chunk of a string — the first i characters.
An analogy. Imagine two grocery lists and you want to edit yours until it matches your roommate's, item by item from the top. At every point you ask: should I cross an item off mine (a delete), jot down a new item from theirs (an insert), or scribble over one of mine to fix it (a replace)? If the next item already matches on both lists, you do nothing and move on for free. The grid records the cheapest total edits to reconcile the first i of your items with the first j of theirs. Each cell looks at three neighbors it already computed — the one up (dp[i-1][j], = delete a letter of A), left (dp[i][j-1], = insert a letter of B), and diagonal up-left (dp[i-1][j-1], = replace, or free if the letters already match) — and takes the cheapest.
One off-by-one warning before the trace: the table has an extra leading row and column for the empty prefix, so cell dp[i][j] actually compares the characters a[i-1] and b[j-1], not a[i] and b[j].
Why it works. Every way to edit A into B must, at its last step, either delete A's last char, insert B's last char, or line the last chars up (matching for free, or replacing). Those three options are exactly the up, left, and diagonal neighbors — each a strictly smaller subproblem we already solved — so taking the cheapest of the three is guaranteed optimal. We fill row by row so a cell's three neighbors are always computed before it.
Why the speed. There are (m+1) × (n+1) cells and each does a constant amount of work (one min over three numbers), giving O(m*n) time, where m and n are the two string lengths. The full table is O(m*n) space, but since each cell only needs the previous row plus the current row's left neighbor, you can keep just two 1-D rows and drop to O(min(m,n)) space. The same grid, with a different rule per cell, also solves Unique Paths, Min Path Sum, Longest Common Subsequence, and Longest Palindromic Subsequence — only the transition changes.
When the answer depends on two moving indices — a position in a grid, or a prefix of each of two strings — your state grows a second dimension: dp[i][j]. The whole game is figuring out which already-solved neighbors up (dp[i-1][j]), left (dp[i][j-1]), and diagonal (dp[i-1][j-1]) feed cell (i,j). On a grid those neighbors are literal squares; on two sequences they mean "I already solved the shorter prefixes." Concrete anchor: Edit Distance turns "horse" into "ros". Each cell asks "cheapest way to make the first i chars of A look like the first j chars of B?" — and the answer is always 1 + min(up, left, diagonal), except the diagonal is free when the two characters already match. Fill the table row by row and the bottom-right corner is your answer. Every problem below is this same table with a different transition.
- Two strings/arrays compared prefix-by-prefix → indices i over A, j over B
- An m x n grid where you only move right/down
- "Min cost / count of ways / longest common ___" between two sequences
- Transform one string into another (insert, delete, replace)
- The recurrence naturally references up, left, or diagonal cells
- Unique Paths / Min Path Sum — grid accumulation: cell + (up or left)
- LCS — match → diag+1, else max(up,left)
- Edit Distance — 1 + min(up,left,diag), diag free on match
- Longest Palindromic Subseq — LCS of s and reversed(s)
def min_distance(a, b):
m, n = len(a), len(b)
# dp[i][j] = edit cost: first i chars of a -> first j chars of b
dp = [[0] * (n + 1) for _ in range(m + 1)]
# base column: turn first i chars into "" => i deletes
for i in range(m + 1):
dp[i][0] = i
# base row: build first j chars from "" => j inserts
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]: # chars match -> diagonal is free
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # up = delete a[i-1]
dp[i][j - 1], # left = insert b[j-1]
dp[i - 1][j - 1], # diag = replace
)
return dp[m][n]
# Rolling array: O(min(m,n)) space — each cell needs only the
# previous row + the current row's left cell, so keep two 1-D rows.
def min_distance_rolling(a, b):
if len(a) < len(b):
a, b = b, a # make b the shorter dimension
m, n = len(a), len(b)
prev = list(range(n + 1)) # base row 0..n
for i in range(1, m + 1):
cur = [i] + [0] * n # cur[0] = i deletes
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[n]function minDistance(a: string, b: string): number {
const m = a.length, n = b.length;
// dp[i][j] = edit cost: first i chars of a -> first j chars of b
const dp: number[][] = Array.from(
{ length: m + 1 },
() => new Array(n + 1).fill(0)
);
for (let i = 0; i <= m; i++) dp[i][0] = i; // i deletes
for (let j = 0; j <= n; j++) dp[0][j] = j; // j inserts
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // match: diagonal free
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // delete
dp[i][j - 1], // insert
dp[i - 1][j - 1], // replace
);
}
}
}
return dp[m][n];
}- Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]; first row & column all 1 (one way along an edge). Min Path Sum: grid[i][j] + min(up, left); edges accumulate the only path.
- LCS: on a char match dp[i][j] = dp[i-1][j-1] + 1 (extend the diagonal), else max(dp[i-1][j], dp[i][j-1]) — drop a char from whichever string and keep the better answer. Base row/column are all 0 (empty prefix shares nothing).
- Longest Palindromic Subsequence: it is exactly LCS(s, reversed(s)) — a palindrome reads the same forward and backward, so the longest subsequence shared with the reverse is the longest palindromic one. (Equivalent interval form: dp[i][j] over substring s[i..j], +2 when ends match, filled by increasing length.)
- Time O(m*n), one pass per cell. Space O(m*n) for the table, or O(min(m,n)) with a rolling two-row (swap so the shorter string is the inner dimension).
- Initialize the first row and column — they encode the cost of building from / collapsing to an empty prefix. Skip them and every later cell reads garbage. For Edit Distance they are 0..i and 0..j; for LCS they are all 0; for Unique Paths all 1.
- String index vs dp index is off by one. Cell dp[i][j] compares a[i-1] and b[j-1], not a[i]/b[j] — the table has an extra leading row/column for the empty prefix.
- The diagonal is the match case. Up/left always represent spending an operation (delete/insert, or dropping a char); the diagonal is where a match lets you carry a result forward for free (LCS +1, Edit Distance +0).
- Answer lives in the bottom-right corner dp[m][n] — the full-prefix-vs-full-prefix cell — for all of these (the interval LPS form reads dp[0][n-1] instead).
Unique paths in an m×n grid — 2-D DP collapsed to one row: