Overview
Many problems need two numbers to describe a subproblem: a position in two different strings, a row and a column of a grid, or an item index and a remaining capacity. The table becomes two-dimensional, but the method is unchanged — define the state, find the recurrence from the last decision, set base cases, and fill the table in a valid order.
Three families cover most interview questions. Grid DP counts or optimises paths. Two-sequence DP compares strings character by character (LCS, edit distance). Knapsack DP decides, for each item, whether to take it given a budget — and with the right loop direction its table compresses to one dimension.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Grid / two-sequence DP | O(m · n) time, O(min(m, n)) space possible |
| 0/1 knapsack | O(n · capacity) |
| Interval DP | O(n³) typically |
Patterns to recognise
Paths in a grid
Use it for: Unique paths, minimum path sum, dungeon game.
Fill row by row; the first row and column are base cases.
Compare two strings
Use it for: LCS, edit distance, distinct subsequences.
Table of size (m + 1) × (n + 1) with empty-prefix base cases.
Subset sum / knapsack
Use it for: Partition equal subset sum, target sum, coin change II.
dp[c] = whether (or how many ways) capacity c can be reached; mind the loop direction.
Code template
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 everything
for j in range(n + 1):
dp[0][j] = j # insert everything
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
dp[i][j - 1], # insert
dp[i - 1][j - 1]) # replace
return dp[m][n]
int minDistance(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 = 0; i <= m; ++i) dp[i][0] = i; // delete everything
for (int j = 0; j <= n; ++j) dp[0][j] = j; // insert everything
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];
}
Common mistakes
- Off-by-one between table indices (prefix length) and string indices (i − 1).
- Iterating knapsack capacity in the wrong direction silently switches between 0/1 and unbounded.
- Allocating a full 2D table when only the previous row is needed can exceed memory limits.
Quick check
Three questions on DP 2D. Get all three right to earn +15 XP.
-
Unique paths in an m x n grid, moving only right or down: dp[r][c] equals:
You arrive at a cell from the cell above or the cell to the left.
-
The standard longest common subsequence table for strings of length m and n takes:
One cell per pair of prefixes, each filled in constant time.
-
In 0/1 knapsack with a 1D array, why iterate capacity from high to low?
Going downward reads values from the previous item only. Going upward would reuse the same item.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Pascal's TriangleLeetCode Easy +20
- Unique PathsLeetCode Medium +40
- Minimum Path SumLeetCode Medium +40
- Longest Common SubsequenceLeetCode Medium +40
- Partition Equal Subset SumLeetCode Medium +40
- Target SumLeetCode Medium +40
- Coin Change IILeetCode Medium +40
- Edit DistanceLeetCode Medium +40
- Longest Palindromic SubsequenceLeetCode Medium +40
- Burst BalloonsLeetCode Hard +70
- Regular Expression MatchingLeetCode Hard +70
Stuck on DP 2D?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor