2D DP kicks in when our state needs two dimensions to describe. Instead of a single array dp[i], we use a matrix dp[i][j]. The value at each cell depends on its neighbors — usually the cell above, to the left, or diagonally.
In simple language, we’re filling a grid instead of a line. Same idea, one extra dimension.
Unique Paths
Problem: We’re at the top-left of an m x n grid. We can only move right or down. How many unique paths to the bottom-right corner?
State: dp[i][j] = number of paths to reach cell (i, j)
Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (came from above or left)
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 |
| 1 | 3 | 6 | 10 |
function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // top + left
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n) — can optimize to O(n)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] # top + left
return dp[m - 1][n - 1]
# Time: O(m*n), Space: O(m*n) — can optimize to O(n)static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int[] row : dp) Arrays.fill(row, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // top + left
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n) — can optimize to O(n)Longest Common Subsequence (LCS)
Problem: Given two strings, find the length of their longest common subsequence. A subsequence doesn’t need to be contiguous — we can skip characters.
Example: "abcde" and "ace" have LCS of "ace" (length 3).
State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
Recurrence:
- If
text1[i-1] == text2[j-1]:dp[i][j] = dp[i-1][j-1] + 1(characters match, extend) - Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(skip one or the other)
| "" | a | b | c | d | e | |
| "" | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 | 2 | 2 |
| e | 0 | 1 | 1 | 2 | 2 | 3 |
function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // match! extend diagonal
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // skip one
}
}
}
return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # match! extend
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # skip one
return dp[m][n]
# Time: O(m*n), Space: O(m*n)static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1; // match! extend
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)Edit Distance (Levenshtein Distance)
Problem: Given two strings, find the minimum number of operations (insert, delete, replace) to convert one into the other. This is a big interview favorite.
State: dp[i][j] = minimum edits to convert word1[0..i-1] into word2[0..j-1]
Recurrence:
- If characters match:
dp[i][j] = dp[i-1][j-1](no edit needed) - Else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])(replace, delete, insert)
function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
new Array(n + 1).fill(0).map((_, j) => (i === 0 ? j : j === 0 ? i : 0))
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // chars match, no edit
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j - 1], // replace
dp[i - 1][j], // delete
dp[i][j - 1] // insert
);
}
}
}
return dp[m][n];
}def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i # deleting all chars
for j in range(n + 1): dp[0][j] = j # inserting 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] # chars match
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete
dp[i][j - 1] # insert
)
return dp[m][n]static int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all
for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[m][n];
}Minimum Path Sum
Problem: Given a grid with non-negative numbers, find the path from top-left to bottom-right that minimizes the sum. We can only move right or down.
This is like unique paths but instead of counting paths, we’re minimizing cost.
State: dp[i][j] = minimum sum to reach cell (i, j)
function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 && j === 0) continue; // starting cell
const top = i > 0 ? grid[i - 1][j] : Infinity;
const left = j > 0 ? grid[i][j - 1] : Infinity;
grid[i][j] += Math.min(top, left); // add cheaper path
}
}
return grid[m - 1][n - 1];
}
// We modified the input grid in-place — O(1) extra space!def min_path_sum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue # starting cell
top = grid[i - 1][j] if i > 0 else float('inf')
left = grid[i][j - 1] if j > 0 else float('inf')
grid[i][j] += min(top, left) # add cheaper path
return grid[m - 1][n - 1]
# We modified the input grid in-place — O(1) extra space!static int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
int top = i > 0 ? grid[i - 1][j] : Integer.MAX_VALUE;
int left = j > 0 ? grid[i][j - 1] : Integer.MAX_VALUE;
grid[i][j] += Math.min(top, left);
}
}
return grid[m - 1][n - 1];
}
// We modified the input grid in-place — O(1) extra space!The 2D DP Pattern
The pattern across all these problems:
- State needs two indices — two strings, grid row/col, two pointers into sequences
- Fill order is top-to-bottom, left-to-right — so dependencies are already computed
- Base cases fill the first row and first column (or the 0th row/column if we use padding)
- Answer is at
dp[m][n](ordp[m-1][n-1]depending on indexing)
Space optimization trick: If each row only depends on the previous row, we can use a 1D array and overwrite it as we go. This drops space from O(m*n) to O(n).