Chapter 4: 2D DP Patterns
Pattern recognition: Two sequences → 2D table indexed by position in each. Grid → 2D table indexed by row, col. The second dimension tracks progress through a second input or a secondary constraint like capacity.
Unique Paths
A robot sits at the top-left corner of an m × n grid and can only move right or down. How many unique paths reach the bottom-right corner?
Subproblem: dp[i][j] = number of paths to cell (i, j).
Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] — arrive from above or from the left. First row and column are all 1.
Example: m = 4, n = 5 → answer 35.
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
Longest Common Subsequence
Given two strings s1 and s2, return the length of their longest common subsequence. A subsequence keeps relative order but skips characters freely.
Example: s1 = "ABCBDAB", s2 = "BDCAB" → answer 4 (e.g. "BCAB").
Derive the formula
LCS is the canonical two-sequence 2D DP. The table dimensions are (|s1| + 1) × (|s2| + 1) to handle empty prefixes cleanly.
Given two strings s1 and s2, what does dp[i][j] represent? Use 1-based indices where dp[i][j] refers to prefixes of length i and j.
Aha: The 2D table is indexed by how much of each string we've processed — not by character positions directly. Row i means "first i characters of s1," column j means "first j characters of s2." This off-by-one padding is what makes the recurrence uniform.
s1[0]='A' ≠ s2[0]='B' → dp[1][1] = max(dp[0][1], dp[1][0]) = max(0, 0) = 0
Code
Edit Distance
Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. You may:
- Insert a character into word1
- Delete a character from word1
- Replace a character in word1
Example: word1 = "horse", word2 = "ros" → answer 3 (horse → rorse → rose → ros).
Edit Distance is LCS's harder sibling. The table structure is identical, but the recurrence adds +1 costs for mismatches instead of taking a max of skips.
What does dp[i][j] represent when transforming word1 into word2 using insert, delete, and replace?
'h' ≠ 'r' → min(ins=2, del=2, rep=1) = 1 (replace)
0/1 Knapsack
Given n items with weights and values, and a knapsack capacity W, maximize total value. Each item can be taken at most once — the 0/1 constraint.
Example: weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 8 → answer 10 (items 0 and 3: 3 + 6).
Given n items with weights and values, and capacity W, what does dp[i][w] represent?
W=1 < weight=2 → skip item0 → dp[1][1] = dp[0][1] = 0
Space optimization: Collapse the 2D table to a 1D array of size W + 1. Iterate capacity right to left when processing each item — this ensures you read from the previous item's row, not the current one. Coin Change iterates left to right because items are unlimited; 0/1 Knapsack iterates right to left because each item is used at most once.
Tips for 2D DP
Two-sequence problems: Add a row and column of base cases for empty prefixes. Characters live at index i-1 when you are at dp[i][j].
Grid problems: First row and column are usually base cases. Interior cells depend on top and left neighbors.
Watch out: For 0/1 Knapsack space optimization, iterating left to right accidentally turns the problem into unbounded knapsack. Always iterate capacity in reverse when each item is single-use.