12.2 2D Grid, String & Subsequence DP

1. Start With a Real Problem: Why Is 1D Not Enough?

In Lesson 12.1, a single number i was enough to describe where we were (dp[i] = best answer for the first i houses).

Now imagine git diff comparing two files, or Google Docs spell-check comparing "horse" and "ros". Can you describe your progress with just one index i? No! Because you are walking through two independent things at the same time:

• You are at index i in text1 AND at index j in text2 (or at row r AND column c in a 2D grid).
• Whenever a subproblem needs two coordinates (i, j) to uniquely identify where you are, your notebook becomes a 2D Table dp[i][j]!

(Important Vocabulary: A Subarray / Substring must be contiguous with no gaps. A Subsequence keeps characters in their original left-to-right order, but is allowed to skip characters in between! In "abcde", "ace" is a subsequence of length 3.)

2. How 2D DP Tables Work: Grid Paths, LCS, and Edit Distance

In every 2D DP problem, cell dp[i][j] is computed from at most three already-solved neighbors right next to it:

• Top (dp[i - 1][j] ↑)
• Left (dp[i][j - 1] ←)
• Top-Left Diagonal (dp[i - 1][j - 1] ↖)

Pattern 1: 2D Grid Path DP (Unique Paths & Minimum Path Sum)

A robot starts at (0, 0) and can only step Right (→) or Down (↓). How can the robot arrive at cell (r, c)?

• Only from the cell directly above it (r - 1, c) or the cell directly to its left (r, c - 1)!
• So dp[r][c] = dp[r - 1][j] + dp[r][c - 1].

Pattern 2: Two-String Alignment (Longest Common Subsequence — LCS)

We allocate a table of size (M + 1) x (N + 1) filled with 0s so Row 0 and Column 0 automatically represent comparing against an empty string "" (base case = 0). When comparing text1[i] and text2[j]:

1. They Match (text1[i] == text2[j]): Both characters pair up! We gain +1 on top of the answer before both characters (Diagonal ↖): dp[i + 1][j + 1] = 1 + dp[i][j]
2. They Differ (text1[i] != text2[j]): They cannot both pair up together. So we try skipping text1[i] (Top ↑) or skipping text2[j] (Left ←) and take the best: dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

Step Through the Visual Drawing Below

Click Next on the interactive stepper below to trace the two cases (Match ↖ vs. Mismatch max(↑, ←)) in the 2D table:

Pattern 3: Edit Distance (Insert, Delete, or Replace)

What if you want the minimum operations to transform word1 into word2?

• If word1[i - 1] == word2[j - 1]: 0 operations needed! Copy the diagonal: dp[i][j] = dp[i - 1][j - 1].
• If they differ, pay 1 operation and take the minimum of all 3 neighbors:
  • dp[i - 1][j] (Top ↑): Delete word1[i - 1].
  • dp[i][j - 1] (Left ←): Insert word2[j - 1].
  • dp[i - 1][j - 1] (Diagonal ↖): Replace word1[i - 1] with word2[j - 1].

3. Longest Increasing Subsequence (LIS): From O(N^2) DP to O(N log N) Binary Search

Given nums = [10, 9, 2, 5, 3, 7, 101, 18], find the length of the longest strictly increasing subsequence ([2, 3, 7, 101] → length 4). Product-company interviewers love asking this in two back-to-back follow-ups:

1. Method 1 — Standard O(N^2) 1D DP:
   • Define dp[i] = length of the longest increasing subsequence ending at index i.
   • Every element by itself has length 1 (dp = [1] * n).
   • For each i, look back at all previous indices j < i: whenever nums[j] < nums[i], we can append nums[i] after nums[j], so dp[i] = max(dp[i], 1 + dp[j]).
2. Method 2 — Optimal O(N log N) Patience Sorting + Binary Search (tails[]):
   • Suppose you have two increasing subsequences of length 2: [2, 5] and [2, 3]. Which one is always better for extending with future numbers? [2, 3], because 3 is smaller than 5!
   • Maintain a sorted list tails, where tails[k] stores the smallest possible ending number of an increasing subsequence of length k + 1.
   • For each number x in nums, use Binary Search (bisect_left / lower_bound) to find the first tail >= x:
     • If x is larger than all tails, append x (extending our longest subsequence by 1!).
     • Otherwise, replace that tail with the smaller x!

4. Basic Operations & Walkthroughs (All 4 Languages)

from bisect import bisect_left

# 1. 2D String DP: Longest Common Subsequence -> O(M * N) Time, O(M * N) Space
def longest_common_subsequence(text1: str, text2: str) -> int:
  m, n = len(text1), len(text2)
  dp = [[0] * (n + 1) for _ in range(m + 1)]
  for i in range(m):
      for j in range(n):
          if text1[i] == text2[j]:
              dp[i + 1][j + 1] = 1 + dp[i][j]
          else:
              dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
  return dp[m][n]

# 2. 2D String DP: Edit Distance (Levenshtein Distance) -> O(M * N)
def min_distance(word1: str, word2: str) -> int:
  m, n = len(word1), len(word2)
  dp = [[0] * (n + 1) for _ in range(m + 1)]
  for i in range(m + 1): dp[i][0] = i
  for j in range(n + 1): dp[0][j] = j
  for i in range(1, m + 1):
      for j in range(1, n + 1):
          if word1[i - 1] == word2[j - 1]:
              dp[i][j] = dp[i - 1][j - 1]
          else:
              dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
  return dp[m][n]

# 3. Longest Increasing Subsequence (LIS) -> Optimal O(N log N)
def length_of_lis(nums: list[int]) -> int:
  tails = []
  for x in nums:
      idx = bisect_left(tails, x)
      if idx == len(tails):
          tails.append(x)
      else:
          tails[idx] = x
  return len(tails)

5. Core Interview Patterns & Common Traps

# Edit Distance (Insert, Delete, or Replace):
for i in range(1, m + 1):
  for j in range(1, n + 1):
      if word1[i - 1] == word2[j - 1]:
          dp[i][j] = dp[i - 1][j - 1]  # Characters match! 0 cost
      else:
          dp[i][j] = 1 + min(
              dp[i - 1][j],      # Delete from word1
              dp[i][j - 1],      # Insert into word1
              dp[i - 1][j - 1],  # Replace character
          )

6. Practice On Your Own (Curated Submodule Problems)