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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the general approach for solving 2D dynamic programming problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “2D DP uses a table dp[i][j] where both dimensions represent a choice or position. The key steps: (1) Define state: what does dp[i][j] represent? (2) Find recurrence: how does dp[i][j] relate to smaller subproblems dp[i-1][j], dp[i][j-1], dp[i-1][j-1]? (3) Base cases: fill dp[0][*] and dp[*][0]. (4) Fill order: usually top-left to bottom-right. (5) Answer: usually dp[m][n] or the max/min over the table. Common patterns: string comparison (LCS, edit distance) — i indexes one string, j the other. Grid navigation (unique paths, minimum path sum) — i,j are coordinates. Knapsack variants — i is item index, j is remaining capacity.”
}
},
{
“@type”: “Question”,
“name”: “How does the Longest Common Subsequence algorithm work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LCS finds the longest sequence of characters appearing in both strings in order (not necessarily contiguous). dp[i][j] = LCS length of s1[:i] and s2[:j]. Recurrence: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (extend the common subsequence). Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one character from either string). Base cases: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0 with anything). Fill row by row. Answer: dp[m][n]. To reconstruct the actual sequence: backtrack from dp[m][n] — if characters matched, include it and go diagonal; else go in the direction of the larger value. Time O(m*n), space O(m*n) or O(min(m,n)) with rolling array.”
}
},
{
“@type”: “Question”,
“name”: “How does the edit distance (Levenshtein distance) algorithm work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Edit distance counts the minimum operations (insert, delete, replace) to transform word1 into word2. dp[i][j] = edit distance between word1[:i] and word2[:j]. Base cases: dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars). Recurrence: 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-1] (replace), dp[i-1][j] (delete from word1), dp[i][j-1] (insert into word1)). The diagonal represents replace, the cell above represents delete, the cell to the left represents insert. Fill row by row. Answer: dp[m][n]. Space can be optimized to O(n) using two rows. Time O(m*n).”
}
},
{
“@type”: “Question”,
“name”: “How do you solve the 0-1 knapsack problem with dynamic programming?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Given items with weights and values, maximize value within a weight capacity W. 0-1 means each item is used at most once. dp[i][w] = max value using items 0..i-1 with weight limit w. Base cases: dp[0][w] = 0 (no items, no value). Recurrence: if items[i-1].weight > w: dp[i][w] = dp[i-1][w] (can’t include item i). Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w – items[i-1].weight] + items[i-1].value). Fill row by row. Answer: dp[n][W]. Space optimization: use a 1D array and fill right to left (prevents using item twice): for w from W down to items[i].weight: dp[w] = max(dp[w], dp[w – items[i].weight] + items[i].value). Time O(n*W), space O(W).”
}
},
{
“@type”: “Question”,
“name”: “How does the burst balloons problem demonstrate interval DP?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Burst Balloons: given balloons with values, bursting balloon i earns nums[i-1]*nums[i]*nums[i+1]. Maximize total coins. Key insight: think about which balloon is burst LAST in an interval [left, right] (not first). dp[left][right] = max coins from bursting all balloons strictly between left and right. For the last balloon k burst in [left, right]: coins = nums[left]*nums[k]*nums[right] + dp[left][k] + dp[k][right]. Try all k as the last balloon. Fill by increasing interval length. This avoids the dependency issue of thinking about which balloon is burst first (its neighbors change). Time O(n^3), space O(n^2). Interval DP pattern: define dp[i][j] as the answer for a subproblem on the range [i,j], and try all split points.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide