2D DP

2D DP models problems where the optimal decision depends on two indices (row/col, i/j in two strings, or two prefixes). The key is to define a clear state meaning, then fill in a table in an order that guarantees prerequisites are already computed.

This module centers on four core patterns: 1) Grid path counting / min-cost (right/down moves). 2) Triangle reduction (bottom-up collapse). 3) Edit distance / alignment (string vs string). 4) Square expansion (largest all-1s square).

Pattern A: Grid DP (count or min)

Use when: you move in constrained directions (right/down) on a grid.

Invariant: dp[r][c] is the correct answer for the subgrid ending at (r,c).

Skeleton (count paths):

DP[0][*] = 1, DP[*][0] = 1 (unless obstacle)
for r in 0..m-1:
    for c in 0..n-1:
        if obstacle: DP[r][c] = 0
        else if r>0 or c>0: DP[r][c] = DP[r-1][c] + DP[r][c-1]

Skeleton (min path sum):

DP[0][0] = grid[0][0]
fill first row/col with cumulative sums
DP[r][c] = min(DP[r-1][c], DP[r][c-1]) + grid[r][c]

Problems:

• unique-paths: pure counting.
• unique-paths-ii: counting with obstacles.
• minimum-path-sum: min-cost variant.

Pattern B: Triangle bottom-up

Use when: each row i only depends on row i+1 (adjacent positions).

Invariant: dp[c] is the minimum total from row r+1 at position c.

Skeleton:

DP = last row
for r from n-2 down to 0:
    for c in 0..r:
        DP[c] = min(DP[c], DP[c+1]) + triangle[r][c]
return DP[0]

Problems:

• triangle: classic bottom-up collapse.

Pattern C: Edit distance / alignment

Use when: you compare two strings and allow insert/delete/replace.

Invariant: dp[i][j] is the edit distance between prefixes word1[:i] and word2[:j].

Skeleton:

DP[0][j] = j, DP[i][0] = i
for i in 1..m:
    for j in 1..n:
        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-1], DP[i-1][j], DP[i][j-1])

Problems:

• edit-distance: canonical alignment DP.

Pattern D: Interleaving DP (two prefixes -> one)

Use when: you must preserve order from two strings to build a third.

Invariant: dp[i][j] is true iff s1[:i] and s2[:j] interleave to s3[:i+j].

Skeleton:

DP[0][0] = true
DP[i][j] = (DP[i-1][j] && s1[i-1] == s3[i+j-1]) ||
           (DP[i][j-1] && s2[j-1] == s3[i+j-1])

Problems:

• interleaving-string: 2D boolean DP (often rolled to 1D).

Pattern E: Largest square of 1s

Use when: you need the largest all-1s square in a binary grid.

Invariant: dp[r][c] is the side length of the largest square ending at (r,c).

Skeleton:

if matrix[r][c] == '1':
    dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])
else: dp[r][c] = 0

Problems:

• maximal-square: classic 3-neighbor min transition.

When to use 2D DP (checklist)

• The decision depends on two indices (grid row/col, or two strings).
• You can define a prefix-based state for both dimensions.
• The transition depends on a small neighborhood (up/left/diag).
• You can fill the table in a consistent order (row-major or reverse).

Common failures (checklist)

• Incorrect base row/column initialization (especially with obstacles).
• Off-by-one in string indices (dp size m+1 by n+1).
• Forgetting to roll the DP when using 1D optimization.
• Using '+' instead of 'min' (or vice versa) for cost/count problems.
• Mixing up "path count" vs "path cost" transitions.

Why these problems fit

• Grid movement -> 2D DP with right/down transitions.
• Triangle -> 2D structure reducible to 1D bottom-up DP.
• Edit distance / interleaving -> two-prefix alignment.
• Maximal square -> 3-neighbor dependency (top/left/diag).