When to Use 2D DP
2D DP uses a table dp[i][j] where i and j represent positions in two sequences, or dimensions of a problem. Common patterns: comparing two strings (LCS, Edit Distance, Regex Matching), 2D grid traversal (unique paths, minimum path sum), unbounded/0-1 knapsack variants, and interval DP (problems on subarrays).
Longest Common Subsequence (LCS)
dp[i][j] = length of LCS of s1[:i] and s2[:j]. Base case: dp[0][j] = dp[i][0] = 0 (empty string). Transition: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Fill row by row. O(m*n) time and space. Space optimization: only need the previous row, O(min(m,n)) space. LCS is the foundation for: Longest Common Substring (track the max while building the table), Shortest Common Supersequence (m+n-LCS), Minimum deletions to make strings equal (m+n-2*LCS).
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[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]Edit Distance (LC 72)
dp[i][j] = minimum operations (insert, delete, replace) to convert s1[:i] to s2[:j]. Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all). Transition: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (no op). Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete from s1, insert into s1, replace). dp[m][n] is the answer. Space: optimize to O(n) using two rows.
0-1 Knapsack
dp[i][w] = max value using items 0..i with weight capacity w. Transition: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w else dp[i-1][w]. O(n*W) time and space. Space optimization: iterate weights in reverse (right to left) to use a 1D array (current item can only use each previous state once). Unbounded knapsack (items can be reused): iterate weights left to right in the 1D array.
Unique Paths (LC 62)
Grid m x n, move only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base case: dp[0][j] = dp[i][0] = 1 (only one way to reach any edge cell). O(m*n) time, O(n) space (single row). With obstacles (LC 63): dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1]. Mathematical formula for LC 62 without DP: C(m+n-2, m-1) — choosing which m-1 of the m+n-2 steps are “down”.
Coin Change II (LC 518) — Unbounded Knapsack Variant
Count number of ways to make amount using coins (unlimited supply). dp[j] = number of ways to make amount j. For each coin: for j from coin to amount: dp[j] += dp[j-coin]. Outer loop over coins, inner over amounts (not the other way) — this ensures each coin can be used unlimited times and combinations are counted without repetition (order does not matter). O(n * amount) time, O(amount) space.
Interval DP: Burst Balloons (LC 312)
dp[i][j] = max coins by bursting all balloons between i and j (exclusive of i and j). For each subproblem size (length of interval), for each k between i and j: dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]). k is the LAST balloon burst in [i+1, j-1] — when k is burst last, i and j are still present as its neighbors. Start from smaller subproblems and build up. O(n^3) time, O(n^2) space.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide