2D DP

1. Introduction

What is 2D DP?

2D DP represents dynamic programming problems where the subproblem states are modeled using two variables, e.g. dp[i][j] represents the optimal solution at grid coordinate (i, j), or the optimal choice considering prefix lengths i of string s1 and j of string s2.

Why study it?

Many optimizations involve relations between two dimensions (like backpack capacity vs items, or string A vs string B alignment). Mastering 2D state transition tables is crucial for advanced pathfinding and string matching interviews.

---

2. Mental Models

0/1 Knapsack: Cap vs Item Decisions

Imagine packing a backpack with items:

For each item i with weight w and value v, at capacity limit c:

- Take item i: Remaining capacity decreases to c - w. Your total value is v + value_with_remaining(i - 1, c - w). - Skip item i: Capacity stays at c. Total value is identical to value_with_remaining(i - 1, c).

Take the maximum: dp[i][c] = max(dp[i-1][c], dp[i-1][c - w] + v).

LCS: String Grid Alignments

Imagine matching characters between two words "abcde" and "ace" on a grid:

If characters match (s1[i] == s2[j]), you extend the matching sequence: dp[i][j] = 1 + dp[i-1][j-1].

If they do not match, you try leaving out a character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

---

3. Core Algorithms & Implementations

1. Unique Paths (LeetCode 62)

State: dp[i][j] = number of unique paths from (0, 0) to (i, j).

Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1].

2. 0/1 Knapsack

State: dp[i][c] = max value using first i items with capacity c.

Recurrence: dp[i][c] = max(dp[i-1][c], dp[i-1][c - wt[i-1]] + val[i-1]) if wt[i-1] <= c.

3. Longest Common Subsequence (LeetCode 1143)

State: dp[i][j] = length of LCS of prefix s1[0...i-1] and s2[0...j-1].

Recurrence:

- dp[i][j] = 1 + dp[i-1][j-1] if s1[i-1] == s2[j-1] - dp[i][j] = max(dp[i-1][j], dp[i][j-1]) if s1[i-1] != s2[j-1]

---

4. Visualizing Subproblem Pruning (LCS)

Table compilation trace of LCS between "abcde" and "ace":

Each cell dp[i][j] holds the optimal common sequence count up to that point. The final result dp[5][3] = 3 represents sequence "ace".

---

5. Real-World Examples

Airline Flight Overbooking: Packing varying business passengers (value) with luggage weight limits into planes (Knapsack).

Git File Version Control: Running LCS on text lines to show deletions/additions between document versions.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test space optimization capabilities:

"Given string LCS, can you reduce the space complexity?"

Optimal Space: Explain that the transition dp[i][j] only requires values from the previous row dp[i-1] and the current row dp[i]. Thus, we can maintain a single 1D array of size N + 1 and update it in-place.

"Why does the Knapsack capacity loop run backwards for (int w = W; w >= wt[i]; w--) in the space-optimized version?"

Backwards Loop Explanation: Running the loop backwards ensures that we update dp[w] using values from the previous item iteration dp[w - wt[i]]. If we ran it forwards, we would overwrite values, leading to multiple uses of the same item (solving the Unbounded Knapsack problem instead of 0/1 Knapsack).

Common Mistakes

> 2. Wrong LCS Indexing: Referencing s1[i] instead of s1[i-1] in 1-indexed DP tables, causing off-by-one errors.

---

7. Summary

Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1].

0/1 Knapsack: dp[w] = max(dp[w], val[i] + dp[w - wt[i]]) (inner loop runs backwards).

LCS: Match leads to 1 + dp[i-1][j-1]; mismatch leads to max(up, left).

---

8. Quiz

Question 1: What is the space complexity of the space-optimized LCS algorithm?

Answer: O(\min(M, N)) space, by allocating the 1D array to match the length of the shorter string.

Question 2: What is the base case value for knapsackTopDown(i, w) when capacity w reaches 0?

Answer: 0. You cannot pack any value when the remaining capacity is 0.

Question 3: If s1 = "apple" and s2 = "pear", what is their LCS length?

Answer: 2 (the subsequence "pe").

Question 4: True or False: 0/1 Knapsack cannot be solved using a Top-Down Memoization approach.

Answer: False. You can solve it using recursive memoization with a cache key representing (itemIndex, remainingCapacity).

Question 5: If grid obstacles are added to Unique Paths, how does the recurrence change?

Answer: If grid[i][j] == obstacle, then dp[i][j] = 0. Otherwise, the recurrence remains dp[i][j] = dp[i-1][j] + dp[i][j-1].