Grid DP (2D): Master Two-Dimensional Dynamic Programming

What is Grid DP?

Grid DP (Two-Dimensional Dynamic Programming) is a pattern where the state is defined on a 2D grid or matrix. The DP table is a 2D array where dp[i][j] represents the optimal solution for a subproblem at position (i, j).

Core Characteristics

Two-Dimensional State: dp[i][j] represents some optimal value at cell (i, j)
Spatial Dependencies: Each cell depends on neighboring cells (above, left, diagonal)
Row-by-Row Iteration: We typically fill the table row by row, left to right
Common Time Complexity: $O(m \times n)$

Two Main Categories

Category	Description	Example
Path Problems	Count/optimize paths in a grid	Unique Paths, Min Path Sum
String DP	Compare two sequences using 2D table	Edit Distance, LCS

Grid Path Problems

Visual Intuition

Unique Paths: Count ways from top-left to bottom-right
              (can only move right or down)

     0   1   2   3
   ┌───┬───┬───┬───┐
 0 │ 1 │ 1 │ 1 │ 1 │  ← First row: only 1 way (all right)
   ├───┼───┼───┼───┤
 1 │ 1 │ 2 │ 3 │ 4 │
   ├───┼───┼───┼───┤
 2 │ 1 │ 3 │ 6 │10 │  → Answer = 10
   └───┴───┴───┴───┘
     ↑
     First column: only 1 way (all down)

dp[i][j] = dp[i-1][j] + dp[i][j-1]
           (from above) + (from left)

Interactive Visualization: Unique Paths

Loading visualization...

Problem 1: Unique Paths (LC 62)

Problem: Count unique paths from top-left to bottom-right. Can only move right or down.

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

Transition:

dp[i][j] = dp[i-1][j] + dp[i][j-1]
           (from above) + (from left)

Base Case: First row and first column are all 1s (only one way to reach them)

Mathematical Solution

This problem is equivalent to choosing which moves are “down” among (m-1+n-1) total moves:

$\binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}$

Problem 2: Unique Paths II (LC 63)

Problem: Same as Unique Paths, but with obstacles (marked as 1).

Key Modification: If a cell is an obstacle, dp[i][j] = 0

Key Insight

Obstacles block paths. Once you hit an obstacle in the first row/column, all cells after it become unreachable from that direction.

Interactive Visualization: Minimum Path Sum

Loading visualization...

Problem 3: Minimum Path Sum (LC 64)

Problem: Find path from top-left to bottom-right with minimum sum. Can only move right or down.

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

Transition:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
           (from above,    from left) + current cell value

Interactive Visualization: Maximal Square

Loading visualization...

Problem 4: Maximal Square (LC 221)

Problem: Find the largest square containing only 1’s, return its area.

State Definition: dp[i][j] = side length of largest square with bottom-right corner at (i, j)

Transition:

if matrix[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
               (above,        left,        diagonal)

Key Insight: Why min()?

The square size is limited by the smallest neighbor:

Case: dp[i-1][j]=3, dp[i][j-1]=2, dp[i-1][j-1]=2

   ┌───┬───┬───┬───┐
   │   │   │   │   │   Even though above has 3×3 square,
   ├───┼───┼───┼───┤   left and diagonal only have 2×2.
   │   │   │ 2 │ 3 │   
   ├───┼───┼───┼───┤   At (i,j), we can only form a 3×3
   │   │   │ 2 │ ? │   square if ALL three neighbors
   └───┴───┴───┴───┘   support it.

   dp[i][j] = min(3, 2, 2) + 1 = 3

String DP (2D Pattern)

String DP uses a 2D table where dp[i][j] represents the answer for s1[0..i-1] and s2[0..j-1].

Visual Intuition: Edit Distance

Convert "horse" to "ros"

         ""  r   o   s
      ┌───┬───┬───┬───┐
   "" │ 0 │ 1 │ 2 │ 3 │  ← Insert r, o, s
      ├───┼───┼───┼───┤
    h │ 1 │ 1 │ 2 │ 3 │  ← h≠r: replace(0+1), delete(1+1), insert(1+1)
      ├───┼───┼───┼───┤
    o │ 2 │ 2 │ 1 │ 2 │  ← o=o: no op needed, take diagonal
      ├───┼───┼───┼───┤
    r │ 3 │ 2 │ 2 │ 2 │  ← r=r: no op needed, take diagonal
      ├───┼───┼───┼───┤
    s │ 4 │ 3 │ 3 │ 2 │  ← s=s: no op needed
      ├───┼───┼───┼───┤
    e │ 5 │ 4 │ 4 │ 3 │  → Answer: 3 operations
      └───┴───┴───┴───┘

Problem 5: Edit Distance (LC 72)

Problem: Find minimum operations (insert, delete, replace) to convert word1 to word2.

State Definition: dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]

Transition:

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]      // No operation needed
else:
    dp[i][j] = 1 + min(
        dp[i-1][j-1],  // Replace word1[i-1] with word2[j-1]
        dp[i-1][j],    // Delete word1[i-1]
        dp[i][j-1]     // Insert word2[j-1]
    )

Understanding the Operations

Operation	Move in DP Table	Meaning
Replace	Diagonal (i-1, j-1) → (i, j)	Change char, advance both
Delete	Up (i-1, j) → (i, j)	Remove from word1, advance word1
Insert	Left (i, j-1) → (i, j)	Add to word1, advance word2

Problem 6: Longest Common Subsequence (LC 1143)

Problem: Find the length of the longest common subsequence of two strings.

State Definition: dp[i][j] = LCS length 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   // Include this char
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // Skip one char

Space Optimization Techniques

Grid DP can often be optimized from $O(m \times n)$ to $O(n)$ or $O(\min(m, n))$ space.

Row-by-Row Optimization

Since we only need the previous row, we can use a single 1D array:

// Before: O(m*n) space
int[][] dp = new int[m][n];
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

// After: O(n) space
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j] + dp[j-1];
        //      ↑ above (previous row's dp[j])
        //             ↑ left (current row's dp[j-1])
    }
}

Key Insight

When we process left-to-right:

dp[j] (before update) = value from previous row = dp[i-1][j]
dp[j-1] (after update) = value from current row = dp[i][j-1]

Common Patterns Summary

Problem Type	State Definition	Transition	Space
Path Counting	`dp[i][j]` = paths to (i,j)	`dp[i-1][j] + dp[i][j-1]`	O(n)
Path Optimization	`dp[i][j]` = min/max to (i,j)	`opt(dp[i-1][j], dp[i][j-1]) + val`	O(n)
Square Finding	`dp[i][j]` = side length at (i,j)	`min(3 neighbors) + 1`	O(n)
String Matching	`dp[i][j]` = answer for s1[0..i], s2[0..j]	depends on char match	O(n)

Iteration Order

For most Grid DP problems, we iterate row by row, left to right:

for i from 0 to m-1:
    for j from 0 to n-1:
        compute dp[i][j]

This ensures that dp[i-1][j] and dp[i][j-1] are computed before dp[i][j].

Exception: Diagonal Filling

Some problems (like Interval DP) require diagonal iteration:

for length from 1 to n:
    for i from 0 to n-length:
        j = i + length - 1
        compute dp[i][j]

Interview Tips

How to Identify Grid DP

Path in a grid → Grid path DP
Compare two strings → String DP (2D table)
Find submatrix with property → Consider dp[i][j] as bottom-right corner

Common Mistakes

Wrong base case: Remember first row and first column often need special handling
Index confusion: Be careful whether dp[i][j] means “first i” or “index i”
Forgetting obstacles: Set dp[i][j] = 0 for blocked cells

Optimization Questions

“Can you reduce space?” → Use 1D array (row optimization)
“What if the grid is huge?” → Stream processing, if applicable
“Can you reconstruct the path?” → Trace back from dp table

Practice Problems

Path Problems

Matrix Problems

String DP (2D)

Summary

Grid DP Key Takeaways:

State is 2D: dp[i][j] represents optimal value at position (i, j) or for prefixes of two sequences
Two main categories:
- Path problems: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
- String problems: dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
Space optimization: Most 2D DP can be reduced to O(n) using row-by-row processing
Iteration order: Row by row, left to right ensures dependencies are met
Base cases: First row and first column often need special initialization

Master these patterns and you’ll handle most Grid DP problems in interviews!