2D Dynamic Programming
When the answer depends on two things at once — a position in each of two strings — the table grows a dimension.
The problem
Two of your teammates edited the same document. You want to know how much they kept in common
— the longest run of characters, in order but not necessarily adjacent, that appears in both
versions. For "ABCBDAB" and "BDCAB" the answer is "BCAB", length 4.
A single index cannot describe where you are here. Your progress is a pair: how far you have read into the first string and how far into the second. The moment a subproblem needs two coordinates to name it, your DP table needs two dimensions.
A first attempt
Recurse on both strings at once. Compare the last characters. If they match, they contribute 1 and you recurse on both shortened strings. If not, you try dropping the last character of each and keep the better result.
def lcs(a, b):
if not a or not b:
return 0
if a[-1] == b[-1]:
return 1 + lcs(a[:-1], b[:-1])
return max(lcs(a[:-1], b), lcs(a, b[:-1]))Correct, but each mismatch branches into two calls, so the tree is roughly O(2^(m+n)).
The pair (i, j) gets revisited a staggering number of times — the classic overlapping
subproblem, now in two dimensions.
The insight
The state is a pair of prefix lengths:
Let
dp[i][j]be the answer for the firsticharacters ofaand the firstjcharacters ofb. There are only(m+1) × (n+1)such pairs — a grid, not a tree.
Each cell depends on its neighbors up and to the left:
j-1 j
+-----+-----+
i-1 | ↖ | ↑ |
+-----+-----+
i | ← | ? |
+-----+-----+If a[i-1] == b[j-1], take the diagonal dp[i-1][j-1] + 1. Otherwise take the better of the
cell above and the cell to the left. Fill the grid row by row and the bottom-right corner is
your answer.
How it works
Define the 2D state
dp[i][j] = length of the longest common subsequence of a[0..i-1] and b[0..j-1]. Using
prefix lengths (not indices) makes the empty-prefix base case clean.
Base row and column
dp[0][j] = 0 and dp[i][0] = 0: matching anything against an empty string yields nothing.
These form the top row and left column that seed everything else.
Recurrence on the last characters
If a[i-1] == b[j-1], the characters pair up: dp[i][j] = dp[i-1][j-1] + 1. Otherwise you
must drop one side: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Fill row by row
Iterate i from 1 to m, and inside it j from 1 to n. Every cell you read (up, left,
diagonal) is already computed. The answer lands in dp[m][n].
The code
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]function lcs(a: string, b: string): number {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}class Solution {
int lcs(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
}int lcs(const char *a, const char *b, int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = 0;
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
}
}
return dp[m][n];
}int lcs(const string &a, const 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++) {
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];
}Complexity
| Approach | Time | Space |
|---|---|---|
| Naive recursion | O(2^(m+n)) | O(m + n) stack |
| 2D DP table | O(m × n) | O(m × n) |
| Two rolling rows | O(m × n) | O(n) |
Because each row depends only on the row above it, you can keep just two rows (or even one, with care) and reduce space to O(n).
When to use it
Two moving parts, two dimensions
Whenever the state is a pair — a position in each of two sequences, an index plus a remaining capacity, a start and an end — reach for a 2D table. The recurrence still combines a constant number of neighboring cells; the grid just makes that geometry visible.
Practice
Recap
- When a subproblem needs two coordinates to name, the DP table gains a dimension.
- The classic 2D recurrence compares last characters: diagonal on a match, else the best of up or left.
- Each row depends only on the previous one, so space collapses from O(m×n) to O(n).
How is this guide?
Last updated on