03 — 2D Grid & String DP

Phase 4 | Week 25–26 | Jan 19 – Feb 1, 2027

Once you’ve internalized 1D DP, extending to 2D is mostly a mechanical step. The state now has two dimensions — usually position in two sequences, or row and column in a grid. The hard part isn’t the code; it’s recognizing which 2D pattern you’re looking at. This file covers four canonical 2D DP problems: grid paths, edit distance, LCS, and the dungeon game. Master these four and you’ve covered 80% of 2D DP on LeetCode.

The 2D DP Mental Model

In 1D DP, dp[i] answered a question about “the first i elements.” In 2D DP, dp[i][j] answers a question about “the first i elements of one thing and the first j elements of another thing” — or “the cell at row i, column j.”

Two flavors:

  1. Grid traversal: dp[i][j] = best answer to reach cell (i, j). Input is a 2D grid.

  2. String/sequence comparison: dp[i][j] = best answer for text1[0..i-1] and text2[0..j-1]. Input is two sequences.

The 5-question framework still applies. The only difference is your state has two indices.

1. Unique Paths (Grid DP)

Problem: An m x n grid. Start top-left, reach bottom-right. Only move right or down. How many unique paths?

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

Transition: You can only arrive from the left (dp[i][j-1]) or from above (dp[i-1][j]):

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base case: First row and first column are all 1 (only one way to reach any cell in the top row or leftmost column — just go straight).

Answer: dp[m-1][n-1]

Table fill (3×3 grid):

1  1  1
1  2  3
1  3  6

2. Unique Paths II (With Obstacles)

Problem: Same grid, but some cells have obstacles. You can’t pass through an obstacle.

Change: If grid[i][j] == 1 (obstacle), then dp[i][j] = 0. Otherwise same transition.

Subtle base case trap: The first row initialization must stop as soon as you hit an obstacle — all cells to the right of the first obstacle in row 0 are unreachable.

for j in range(n):
    if grid[0][j] == 1:
        break
    dp[0][j] = 1

3. Minimum Path Sum

Problem: Grid with non-negative integers. Move right or down only. Find path with minimum sum from top-left to bottom-right.

State: dp[i][j] = minimum path sum to reach (i, j).

Transition:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Base case: dp[0][0] = grid[0][0]. First row and first column are prefix sums.

This is identical in structure to Unique Paths — just swap “count paths” for “minimize cost.”

4. Edit Distance (The Canonical 2D String DP)

Edit distance (Levenshtein distance) is the number of single-character edits (insert, delete, replace) needed to transform word1 into word2. This is used in spell checkers, DNA alignment, and diff tools.

State: dp[i][j] = minimum edit distance between word1[0..i-1] and word2[0..j-1].

Base cases:

  • dp[0][j] = j: transforming empty string to word2[0..j-1] requires j insertions.

  • dp[i][0] = i: transforming word1[0..i-1] to empty string requires i deletions.

Transition:

If word1[i-1] == word2[j-1], no operation needed:

dp[i][j] = dp[i-1][j-1]

If they differ, take the minimum of the three operations:

dp[i][j] = 1 + min(
    dp[i-1][j],    # delete from word1 (or insert into word2)
    dp[i][j-1],    # insert into word1 (or delete from word2)
    dp[i-1][j-1]   # replace
)

Full example: word1 = "horse", word2 = "ros"

    ""  r   o   s
""   0   1   2   3
h    1   1   2   3
o    2   2   1   2
r    3   2   2   2
s    4   3   3   2
e    5   4   4   3

Answer: dp[5][3] = 3. Operations: replace h→r, delete r, delete e.

Backtracking the solution (optional): To reconstruct the edit sequence, trace back from dp[m][n]:

  • If word1[i-1] == word2[j-1]: go diagonal (no op)

  • If dp[i][j] == dp[i-1][j] + 1: came from delete

  • If dp[i][j] == dp[i][j-1] + 1: came from insert

  • If dp[i][j] == dp[i-1][j-1] + 1: came from replace

Space optimization: Since each row only depends on the previous row, you can do it in O(min(m,n)) space. Maintain two rows or a 1D array updated carefully.

5. Longest Common Subsequence (LCS)

LCS vs. Longest Common Substring: This trips up almost everyone.

  • LCS (subsequence): Characters don’t need to be contiguous. “ace” is a subsequence of “abcde”.

  • Longest Common Substring: Characters MUST be contiguous. Different recurrence, different answer.

Keep these distinct. The problem statement will say “subsequence” or “substring” — read carefully.

LCS State: dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1].

Transition:

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base case: dp[0][j] = 0, dp[i][0] = 0 (empty string has LCS of 0 with anything).

Example: text1 = "abcde", text2 = "ace"

    ""  a   c   e
""   0   0   0   0
a    0   1   1   1
b    0   1   1   1
c    0   1   2   2
d    0   1   2   2
e    0   1   2   3

Answer: 3 (“ace”).

Space optimization: The recurrence uses dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. You can optimize to O(n) space with careful 1D array + a prev variable tracking the diagonal.

6. Longest Common Substring

State: dp[i][j] = length of the longest common substring ending at text1[i-1] and text2[j-1].

Key difference from LCS: The substring must end here. If characters don’t match, the substring breaks — you set dp[i][j] = 0, not max(...).

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
    result = max(result, dp[i][j])
else:
    dp[i][j] = 0   # <-- NOT max(dp[i-1][j], dp[i][j-1])

The answer is max(dp[i][j]) over all i, j — not dp[m][n].

7. Dungeon Game (Backward DP)

Problem: Knight starts top-left, princess at bottom-right. Grid has positive and negative values. Knight must have at least 1 health at every cell. Find minimum initial health.

Why forward DP fails: At any cell, the decision depends on both what we’ve gained AND what we need in the future. A greedy forward pass doesn’t capture future requirements.

Insight: Fill the DP table from bottom-right to top-left. dp[i][j] = minimum health needed entering cell (i, j) to survive to the end.

Transition:

min_health_on_exit = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, min_health_on_exit - dungeon[i][j])

The max(1, ...) ensures health never drops below 1.

Base case: dp[m][n] (princess cell) = max(1, 1 - dungeon[m-1][n-1]). Knight needs at least 1 health there.

This is the core lesson: when future constraints govern decisions, fill the table backward.

What Most Engineers Get Wrong

1. Confusing LCS and Longest Common Substring. LCS uses max(dp[i-1][j], dp[i][j-1]) when characters don’t match. Substring uses dp[i][j] = 0. Swapping these gives wrong answers with no compile error — silent, insidious bug.

2. Off-by-one in table dimensions. For text1 of length m and text2 of length n, the DP table is (m+1) x (n+1), not m x n. The extra row/column holds the base cases for empty strings. Skipping this means your base cases corrupt actual data.

3. Incorrect space optimization for edit distance. If you’re compressing to 1D, the dp[i-1][j-1] (diagonal) value gets overwritten before you use it. You need a prev variable to save it before updating in-place.

Practice Problems

Easy

  1. Unique Paths — LeetCode 62. Classic 2D grid. Baseline.

  2. Minimum Path Sum — LeetCode 64. Grid with costs. Same structure as Unique Paths.

  3. Longest Common Subsequence — LeetCode 1143. The canonical LCS.

Medium

  1. Unique Paths II — LeetCode 63. Obstacles. Tests your base case initialization.

  2. Edit Distance — LeetCode 72. Memorize this recurrence. It appears in interviews verbatim.

  3. Maximal Square — LeetCode 221. Find the largest square of 1s. State design is non-obvious.

  4. Interleaving String — LeetCode 97. Is s3 an interleaving of s1 and s2? 2D DP where the state tracks positions in both strings.

Hard

  1. Dungeon Game — LeetCode 174. Forces you to think backward. Tests whether you’ve internalized the “fill from where?” question.