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.

📐
The key insight
Two changing variables = two dimensions in your DP table
  • Two strings: Comparing "ABCDE" with "ACE" → dp[i][j] where i = position in string 1, j = position in string 2 (LCS, edit distance).
  • Items + capacity: Choosing items with a weight limit → dp[i][w] where i = 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.
The 2D DP recipe:
(1) Define what 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

A B C D E A C E 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 2 2 2 0 1 1 2 2 3 Base = 0 Match → diagonal + 1 Skip → max(left, above)
Match (diagonal + 1) Skip (max of left, above) Final answer Base case (0)

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.

lcs.py O(m*n) time, O(m*n) space
Output
3 3 0 3

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.
Why subsequence, not substring?
A subsequence can skip characters but must maintain order. "ACE" is a subsequence of "ABCDE" (skip B and D). A substring must be contiguous — "ABC" is a substring of "ABCDE" but "ACE" is not.

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").

🎒
The intuition
For each item: take it or leave it

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).
knapsack.py O(n*W) time, O(n*W) space
Output
Max value: 22 Max value: 7
0/1 vs Unbounded knapsack:
In 0/1 knapsack, each item is used at most once — the recurrence looks at 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.

lis_dp.py O(n²) time, O(n) space
Output
4 4 1

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.

lis_binary_search.py O(n log n) time, O(n) space
Output
4 4 1 4
Why O(n log n)?
The 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
edit_distance.py O(m*n) time, O(m*n) space
Output
3 5 3 0
Tracing the edits for "horse" → "ros":
horse → rorse (replace h with r) → rose (delete r at index 2) → ros (delete e). Three operations total.

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

lcs_optimized.py O(m*n) time, O(n) space
Output
3 0

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.

knapsack_optimized.py O(n*W) time, O(W) space
Output
Max value: 22 Max value: 7
Why reverse iteration for 0/1 knapsack?
If you iterate left to right, 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:

🎯
Pattern cheat sheet
Match the problem to the DP pattern
  • Linear DP (1D): Climbing stairs, house robber, maximum subarray. State depends on a single index. dp[i] uses dp[i-1] and/or dp[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

  1. "Maximum/minimum value" or "count the ways" → likely DP (not backtracking).
  2. Two strings/sequences? → 2D string DP (LCS, edit distance).
  3. Items with weight/cost limit? → Knapsack. Can reuse items? Unbounded. Can't? 0/1.
  4. "Longest increasing..." → LIS pattern.
  5. Subsets that sum to target? → 0/1 knapsack variant (subset sum).
Interview strategy:
When you see a DP problem, first ask: what are the changing variables? If one variable changes → 1D DP. If two variables change → 2D DP. Define 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

Advanced DP Challenges
Challenge 1: Coin Change II — Unbounded Knapsack (LeetCode 518)

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].

This is unbounded knapsack for counting. Use 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.
Challenge 2: Palindrome Partitioning II (LeetCode 132)

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"]).

Use two DP arrays. First, precompute a 2D boolean 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

Question 1 of 5
In the LCS DP table, what do you do when the characters at positions i and j match?
Question 2 of 5
In the 0/1 knapsack space-optimized version (1D array), why must you iterate capacity in reverse?
Question 3 of 5
What is the time complexity of the binary search approach for Longest Increasing Subsequence?
Question 4 of 5
In the edit distance problem, which three operations does the recurrence consider?
Question 5 of 5
A problem says: "Given items with weights and values, each item can be used unlimited times, maximize total value." Which DP pattern is this?
0
/5
Great work! You understand advanced DP patterns.

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 m and n, 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] = i and dp[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.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →