From 1D to 2D: When You Need Two Dimensions
In the DP basics lesson, every problem used a single array dp[i] where i tracked one variable (position in array, amount of money, stair number). But many interview problems involve two sequences or two constraints — and that's when you need a 2D table.
- Two strings: Comparing "ABCDE" with "ACE" →
dp[i][j]wherei= position in string 1,j= position in string 2 (LCS, edit distance). - Items + capacity: Choosing items with a weight limit →
dp[i][w]wherei= item index,w= remaining capacity (knapsack). - Subsequence + length: Building the longest increasing subsequence → can be done in 1D, but understanding the 2D framing helps you see the pattern.
dp[i][j] means in plain English. (2) Write the recurrence — how does dp[i][j] relate to smaller subproblems? (3) Identify base cases (first row, first column). (4) Fill the table row by row. (5) The answer is at dp[m][n] (bottom-right corner).
2D DP Table: LCS of "ABCDE" and "ACE"
The Longest Common Subsequence (LCS) is the classic 2D DP problem. Given two strings, find the longest sequence of characters that appears in both (in order, but not necessarily contiguous). For "ABCDE" and "ACE", the LCS is "ACE" with length 3.
Step-by-step: filling the LCS DP table
The recurrence is simple: if s1[i-1] == s2[j-1], take the diagonal value + 1 (we found a match). Otherwise, take the max of the cell above or to the left (skip one character from either string).
Problem: Longest Common Subsequence
Given two strings, return the length of their longest common subsequence. This is LeetCode 1143 and appears in interviews at Google, Amazon, and Microsoft.
Complexity
- Time: O(m × n) — we fill every cell in the m × n table exactly once.
- Space: O(m × n) for the table. We'll optimize this to O(n) later with rolling arrays.
0/1 Knapsack Pattern
The knapsack problem is the most fundamental DP pattern after Fibonacci. You have n items, each with a weight and value. You can carry at most W weight. Maximize the total value. Each item can be taken at most once (that's the "0/1").
dp[i][w] = maximum value using items 0..i with capacity w. For each item, you have two choices:
- Skip it:
dp[i][w] = dp[i-1][w](same value without this item). - Take it (if it fits):
dp[i][w] = dp[i-1][w - weight[i]] + value[i]. - Pick the better option:
dp[i][w] = max(skip, take).
dp[i-1][...] (previous row). In unbounded knapsack (items can be reused), you look at dp[i][...] (current row), allowing the same item again. The challenge problems cover unbounded knapsack.
Problem: Longest Increasing Subsequence
Given an integer array, find the length of the longest strictly increasing subsequence. This is LeetCode 300 — one of the most-asked DP problems. We'll cover both the O(n²) DP approach and the O(n log n) binary search optimization.
Approach 1: O(n²) DP
dp[i] = length of the LIS ending at index i. For each i, look at all previous elements j < i: if nums[j] < nums[i], we can extend that subsequence.
Approach 2: O(n log n) with Binary Search
Maintain a "tails" array where tails[k] is the smallest possible tail element for an increasing subsequence of length k+1. For each number, use binary search to find where it fits.
tails array is always sorted, so bisect_left runs in O(log n). We process each of the n elements once, giving O(n log n) total. This is optimal for LIS.
Problem: Edit Distance
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 into word2. This is LeetCode 72 and the classic string DP problem. It's used in spell checkers, DNA sequence alignment, and diff tools.
dp[i][j] = minimum edits to convert word1[:i] to word2[:j]. The recurrence:
- If
word1[i-1] == word2[j-1]: no edit needed →dp[i][j] = dp[i-1][j-1] - Otherwise, take the minimum of three operations:
- Insert:
dp[i][j-1] + 1 - Delete:
dp[i-1][j] + 1 - Replace:
dp[i-1][j-1] + 1
- Insert:
Space Optimization: Rolling Array
Every 2D DP solution we've seen has O(m × n) space. But look at the recurrences: dp[i][j] only depends on dp[i-1][...] (the previous row) and dp[i][j-1] (the current row, left). This means we only need two rows at a time — or even just one row with a temp variable.
LCS with O(n) Space
0/1 Knapsack with O(W) Space
For knapsack, we can use a single 1D array — but we must iterate capacity in reverse to avoid using an item twice in the same row.
dp[w - weight[i]] may already include item i from this iteration — effectively allowing unlimited uses. Reverse iteration ensures we read values from the "previous row" (before item i was considered). For unbounded knapsack, iterate left to right intentionally.
DP Pattern Recognition
The hardest part of DP isn't coding the solution — it's recognizing which pattern to use. Here's a cheat sheet for the most common DP families:
- Linear DP (1D): Climbing stairs, house robber, maximum subarray. State depends on a single index.
dp[i]usesdp[i-1]and/ordp[i-2]. - Two-string DP (2D): LCS, edit distance, regex matching. Compare characters from two sequences.
dp[i][j]uses diagonal, above, and left. - 0/1 Knapsack: Subset sum, partition equal subset, target sum. Binary choice per item (take/skip) with a capacity constraint.
- Unbounded Knapsack: Coin change, rod cutting, ribbon cutting. Items can be reused. Forward iteration in 1D array.
- LIS-type: Longest increasing subsequence, longest chain, Russian doll envelopes. Build sequences with ordering constraints.
- Interval DP: Matrix chain multiplication, palindrome partitioning, burst balloons. State is a range
[i..j].
How to identify the right pattern
- "Maximum/minimum value" or "count the ways" → likely DP (not backtracking).
- Two strings/sequences? → 2D string DP (LCS, edit distance).
- Items with weight/cost limit? → Knapsack. Can reuse items? Unbounded. Can't? 0/1.
- "Longest increasing..." → LIS pattern.
- Subsets that sum to target? → 0/1 knapsack variant (subset sum).
dp[...] in plain English, write the recurrence, then code it.
Try It Yourself
Find the Longest Common Subsequence
Complete the lcs() function that returns both the length and the actual LCS string for two input strings. Use the 2D DP table approach, then backtrack through the table to reconstruct the subsequence.
Challenge
Given an array of coin denominations coins and a target amount, return the number of combinations that make up that amount. Each coin can be used unlimited times.
Example: coins = [1, 2, 5], amount = 5 → 4 combinations: [5], [2+2+1], [2+1+1+1], [1+1+1+1+1].
dp[j] = number of ways to make amount j. Base case: dp[0] = 1 (one way to make 0: use no coins). For each coin, iterate j from coin to amount (left to right — unbounded!). dp[j] += dp[j - coin]. Iterate coins in the outer loop to avoid counting [1,2] and [2,1] as different combinations.Given a string s, return the minimum number of cuts needed so that every substring partition is a palindrome.
Example: "aab" → 1 cut (["aa", "b"]).
is_pal[i][j] = whether s[i..j] is a palindrome. Then use dp[i] = minimum cuts for s[0..i]. For each position i, try every j from 0 to i: if s[j..i] is a palindrome, then dp[i] = min(dp[i], dp[j-1] + 1). Base case: if the entire prefix s[0..i] is already a palindrome, dp[i] = 0.Quiz
Common Mistakes
- Wrong iteration direction in space-optimized knapsack. Iterating left to right in the 0/1 knapsack 1D array lets you reuse items (turning it into unbounded knapsack). Always iterate capacity in reverse for 0/1 problems.
- Off-by-one in 2D DP table dimensions. If strings have lengths
mandn, your table should be(m+1) x (n+1)to accommodate the empty-string base cases. Forgetting the +1 causes index errors. - Confusing subsequence with substring. LCS finds the longest common subsequence (characters don't need to be contiguous). If you need the longest common substring, the recurrence resets to 0 on mismatch instead of taking max(above, left).
- Not initializing base cases for edit distance. The first row and first column represent converting to/from the empty string.
dp[i][0] = ianddp[0][j] = j. Forgetting these gives wrong answers for any string that starts with matching characters. - Using the wrong knapsack variant. If items can be reused (coins, rod cutting), use unbounded knapsack (forward iteration). If each item is used at most once (subset sum, 0/1), use reverse iteration. Mixing them up is the most common DP bug in interviews.
Key Takeaways
- 2D DP tables handle problems with two changing variables (two strings, items + capacity). Define
dp[i][j]clearly, write the recurrence, fill row by row. - LCS and Edit Distance are the two canonical string DP problems. Both use a 2D table comparing characters from two strings. Match = diagonal; skip = max/min of above and left.
- 0/1 Knapsack is the template for "take or skip" problems with a capacity constraint. Subset sum, partition equal subset, and target sum are all knapsack variants.
- LIS has two approaches: O(n²) DP for simplicity and O(n log n) binary search for optimal performance. The binary search approach using a "tails" array is worth memorizing.
- Space optimization with rolling arrays reduces O(m×n) space to O(n) for any 2D DP where each row only depends on the previous row. For knapsack, iterate in reverse; for unbounded, iterate forward.
You've conquered advanced DP.
Now let it conquer interviews for you.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →