2-Dimensional DP
Solving problems with 2D state spaces. Grid paths, edit distance, and longest common subsequence.
When problems have two dimensions of state (like two strings or a grid), we use 2D dynamic programming. The table becomes a 2D array where dp[i][j] depends on smaller subproblems.
2D DP Template
def solve_2d_dp(m, n):
# Create 2D table
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Fill base cases
for i in range(m + 1):
dp[i][0] = base_value_row
for j in range(n + 1):
dp[0][j] = base_value_col
# Fill table
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
Problem: Unique Paths
Count paths from top-left to bottom-right moving only right or down:
Grid (3x3):
S → → →
↓ ↓ ↓
↓ ↓ ↓
↓ → → E
dp[i][j] = dp[i-1][j] + dp[i][j-1]
(paths from above + paths from left)
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Space-optimized
def unique_paths_optimized(m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[n-1]
Problem: Minimum Path Sum
Find path with minimum sum from top-left to bottom-right:
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# First row
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# First column
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Fill rest
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
Problem: Longest Common Subsequence (LCS)
Find the longest subsequence common to both strings:
s1 = "abcde", s2 = "ace"
LCS = "ace" (length 3)
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
fn longest_common_subsequence(text1: &str, text2: &str) -> usize {
let chars1: Vec<char> = text1.chars().collect();
let chars2: Vec<char> = text2.chars().collect();
let m = chars1.len();
let n = chars2.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
if chars1[i - 1] == chars2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
}
}
}
dp[m][n]
}
LCS Recurrence
If characters match: dp[i][j] = dp[i-1][j-1] + 1 (extend the LCS). If not: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take best without one character).
Problem: Edit Distance
Minimum operations (insert, delete, replace) to convert one string to another:
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Base cases
for i in range(m + 1):
dp[i][0] = i # Delete all chars
for j in range(n + 1):
dp[0][j] = j # Insert all chars
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # No operation needed
else:
dp[i][j] = 1 + min(
dp[i-1][j], # Delete
dp[i][j-1], # Insert
dp[i-1][j-1] # Replace
)
return dp[m][n]
word1 = "horse", word2 = "ros"
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
Answer: 3 (replace h→r, delete r, delete e)
Problem: 0/1 Knapsack
Choose items to maximize value without exceeding weight capacity:
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Don't take item i
dp[i][w] = dp[i-1][w]
# Take item i if possible
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Space-optimized (traverse backwards)
def knapsack_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
Why Traverse Backwards?
In space-optimized 0/1 knapsack, we traverse capacity backwards to ensure we don't use the same item twice. Forward traversal would use already-updated values.
Problem: Longest Palindromic Subsequence
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
# Base case: single characters
for i in range(n):
dp[i][i] = 1
# Fill for increasing lengths
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
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]
Problem: Maximal Square
Find largest square containing only 1s:
def maximal_square(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
Common 2D DP Patterns
| Pattern | Example | Key Insight | |---------|---------|-------------| | Grid paths | Unique Paths | dp[i][j] = dp[i-1][j] + dp[i][j-1] | | String matching | LCS, Edit Distance | Compare characters | | Interval DP | Palindrome | dp[i][j] for substring i..j | | Knapsack | 0/1 Knapsack | Include or exclude item | | Matrix | Maximal Square | dp[i][j] depends on 3 neighbors |
Space Optimization
Many 2D DP problems only need the previous row:
# Original: O(m×n) space
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Optimized: O(n) space
dp = [0] * (n + 1)
# For some problems, O(1) variables suffice
prev_row = [...]
curr_row = [...]
Key Takeaways
- 2D DP uses a 2D table where dp[i][j] solves subproblem (i, j)
- Common patterns: grid paths, string matching, intervals, knapsack
- Identify base cases for edges of the table
- Determine fill order (usually row by row, left to right)
- Space can often be optimized to O(n) or O(1)
- Visualize the table to understand the recurrence
2D DP is powerful for problems involving pairs of sequences, grids, or two dimensions of choice. The key is defining what dp[i][j] represents and finding how it depends on smaller subproblems.