Dynamic Programming: 2D
On this page
Two-dimensional DP is the same method as DP 1D, with one more number in the state. A subproblem is now "the first i characters of one string and the first j of the other", or "the cell at row r, column c", or "the substring from i to j". The table is a grid, and each cell is filled from a few neighbours that are already done.
When to recognise it
- A grid with "number of paths", "minimum path sum", "largest square":
dp[r][c]comes from the cell above and the cell to the left. - Two strings or sequences: longest common subsequence, edit distance, interleaving, wildcard or regex matching.
dp[i][j]coversa[:i]andb[:j]. - A substring or range of one string: longest palindromic substring or subsequence, burst balloons.
dp[i][j]coverss[i..j], filled by increasing length. - Knapsack: items × capacity. "Can I pick items summing to target?" (partition equal subset sum) is a 2D table that is usually squeezed into one row.
Shape 1: grid paths
Paths into a cell = paths from above + paths from the left. Walls contribute 0.

def unique_paths(grid):
"""Grid DP: paths into a cell = paths from above + paths from the left. '#' is a wall."""
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if grid[r][c] == '#':
continue
if r == 0 and c == 0:
dp[r][c] = 1
continue
dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
return dp[-1][-1]
Time and space O(rows × cols). Only the previous row is needed, so one row of length cols is enough.
Shape 2: two strings
Make the table one row and one column bigger than the strings. Row 0 and column 0 stand for the empty prefix, and they hold the base cases.

def lcs(a, b):
"""Two-string DP: dp[i][j] = answer for a[:i] and b[:j]. Row 0 and column 0 are empty prefixes."""
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 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[-1][-1]
Edit distance has the same shape with three choices. Each row only reads the row above, so this version keeps one previous row:
def edit_distance(a, b):
"""Same table shape. Base cases: turning a prefix into '' costs its length."""
prev = list(range(len(b) + 1)) # row i-1, kept as one array to save space
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete a[i-1]
cur[j - 1]) # insert b[j-1]
prev = cur
return prev[-1]
Time O(m × n), space O(n) with the rolling row.
Shape 3: substrings
For substrings, dp[i][j] depends on dp[i + 1][j − 1], the shorter range inside it, so you fill by increasing length. For the longest palindromic substring there is a simpler O(n²) method with O(1) space: treat each of the 2n − 1 centres as the middle and expand outward while the ends match.
def longest_palindrome(s):
"""Interval DP alternative: expand around each of the 2n - 1 centres, O(n^2) time, O(1) space."""
best = ''
for centre in range(2 * len(s) - 1):
lo, hi = centre // 2, centre // 2 + centre % 2
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo, hi = lo - 1, hi + 1
if hi - lo - 1 > len(best):
best = s[lo + 1:hi]
return best
Mention both: the table version shows the DP idea, and expanding around centres is what you'd actually write.
How to fill the table without mistakes
- Say the state in a sentence: "
dp[i][j]is the edit distance betweena[:i]andb[:j]." - Fill row 0 and column 0 from that sentence (turning a prefix into the empty string costs its length).
- Write the recurrence for one inner cell, with the letters
a[i − 1]andb[j − 1]. - Check one cell by hand on a tiny example before coding the loops.
Common bugs
- Index shift:
dphas one extra row and column, so the characters area[i − 1]andb[j − 1]. Mixing these is the most common 2D bug. - Building rows with
[[0] * n] * min Python: every row is the same list. Use a list comprehension. - Wrong fill order for substrings: looping
iupward readsdp[i + 1][…]before it is filled. Loop by length, oridownward. - Rolling arrays overwriting values you still need: for LCS with one row, save the old diagonal value before you overwrite it.
- Mixing up subsequence and substring: a subsequence may skip characters, a substring may not. The recurrences differ.
Say this in the interview
- "Let dp[i][j] be the answer for the first i letters of a and the first j letters of b. If the last letters match, it's dp[i − 1][j − 1]; otherwise I try each operation and take the best."
- "Each cell takes O(1), so O(m × n) time. Each row only needs the one above, so I can cut space to O(n)."
Problems for this pattern
- Unique Paths: grid paths.
- Longest Common Subsequence: two strings.
- Longest Palindromic Substring: substrings, or expand around centres.
- Partition Equal Subset Sum: knapsack in one row.
- Maximal Square: 1 + min of three neighbours.
- Edit Distance: two strings, three choices.
- Regular Expression Matching: two strings with a star rule, the hard one.
Related
DP 1D · Backtracking · Arrays and Strings · Pattern Recognition Cheat Sheet