2D DP — Grids & Strings
Grid path DP, and the two-sequence family — longest common subsequence, edit distance, distinct subsequences, regex/wildcard matching — plus palindromic substring DP.
Grid DP
The state is a cell, and moves are restricted (usually right/down), so the grid is a DAG and each cell depends on already-computed neighbours.
def unique_paths_with_obstacles(grid):
R, C = len(grid), len(grid[0])
dp = [0] * C # one row, updated in place
dp[0] = 1
for r in range(R):
for c in range(C):
if grid[r][c] == 1:
dp[c] = 0
elif c > 0:
dp[c] += dp[c - 1] # dp[c] (from above) + dp[c-1] (from left)
return dp[-1]
int uniquePathsWithObstacles(vector<vector<int>>& g) {
int R = g.size(), C = g[0].size();
vector<long long> dp(C, 0);
dp[0] = 1;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (g[r][c]) dp[c] = 0;
else if (c > 0) dp[c] += dp[c - 1];
}
return dp[C - 1];
}
Maximal square
The largest square with bottom-right corner at (r, c) is limited by its three neighbours:
def maximal_square(matrix):
R, C = len(matrix), len(matrix[0])
dp = [[0] * (C + 1) for _ in range(R + 1)]
best = 0
for r in range(1, R + 1):
for c in range(1, C + 1):
if matrix[r - 1][c - 1] == "1":
dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
best = max(best, dp[r][c])
return best * best
Going backwards
When the constraint depends on the future (minimum starting health in Dungeon Game), fill the table from the destination back to the start.
Multiple walkers
Two robots moving simultaneously (Cherry Pickup) → state holds both positions: dp[row][c1][c2]. Keeping them in the same row (or same step count) keeps the state small.
The two-sequence family
State dp[i][j] = answer for the prefixes a[:i] and b[:j]. Transitions look at the last characters a[i−1] and b[j−1]. Row 0 and column 0 represent empty prefixes.
Longest common subsequence
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
int longestCommonSubsequence(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1
: max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
Step through this exact table in the DP visualizer, including the backtrack that recovers the subsequence.
LCS derivatives:
| Problem | Formula |
|---|---|
| min deletions to make equal | m + n − 2·LCS |
| shortest common supersequence length | m + n − LCS |
| longest palindromic subsequence | LCS(s, reverse(s)) |
| min insertions to make palindrome | n − LPS |
| Uncrossed Lines | exactly LCS |
Edit distance
Operations: insert, delete, replace (each cost 1).
def min_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # delete all of a[:i]
for j in range(n + 1):
dp[0][j] = j # insert all of b[:j]
for i in range(1, m + 1):
for j in range(1, n + 1):
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
)
return dp[m][n]
int minDistance(string a, string b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = a[i - 1] == b[j - 1]
? dp[i - 1][j - 1]
: 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
return dp[m][n];
}
Distinct subsequences (counting)
How many times does t appear as a subsequence of s?
def num_distinct(s, t):
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1 # empty t: one way (delete everything)
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j] # skip s[i-1]
if s[i - 1] == t[j - 1]:
dp[i][j] += dp[i - 1][j - 1] # use s[i-1] to match t[j-1]
return dp[m][n]
Pattern matching
Wildcard (? = one char, * = any sequence):
def is_match_wildcard(s, p):
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and p[j - 1] == "*"
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
dp[i][j] = dp[i][j - 1] or dp[i - 1][j] # * matches empty, or one more char
elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
Regex (. = any char, x* = zero or more of x):
def is_match_regex(s, p):
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(2, n + 1):
dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
dp[i][j] = dp[i][j - 2] # zero copies of x
if p[j - 2] in (s[i - 1], "."):
dp[i][j] = dp[i][j] or dp[i - 1][j] # one more copy of x
elif p[j - 1] in (s[i - 1], "."):
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
Palindromes: substring DP
pal[i][j] = is s[i..j] a palindrome? It depends on pal[i+1][j−1], so fill by increasing length (or i descending).
def count_substrings(s):
n = len(s)
pal = [[False] * n for _ in range(n)]
count = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]):
pal[i][j] = True
count += 1
return count
The center expansion approach does the same in O(1) extra space (see Arrays & Strings).
Longest palindromic subsequence (not contiguous):
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
This “substring [i..j]” state is the gateway to interval DP.
Space optimization for 2D DP
When row i only needs row i−1, keep two rows (or one row plus a saved diagonal):
def lcs_1d(a, b):
n = len(b)
dp = [0] * (n + 1)
for i in range(1, len(a) + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if a[i - 1] == b[j - 1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j - 1])
diag = temp
return dp[n]
Put the shorter string on the column axis to minimize memory.
Common mistakes
- Off-by-one between string index
i−1and table indexi. - Forgetting the empty-prefix row/column initialization.
- Palindrome table filled in an order where
pal[i+1][j−1]isn't ready yet. - Regex:
*refers to the preceding char, so look atp[j−2]. - Losing the diagonal value when compressing to one row.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.