2D Dynamic Programming (Grid Paths)

Grid path problems are a classic example of two-dimensional dynamic programming, where the state depends on both row and column indices. These problems teach how to build solutions over a grid and are foundational for many real-world path and matrix problems.

Problem Statement

You are given an m × n grid.

• You start at the top-left corner (0, 0)
• You want to reach the bottom-right corner (m - 1, n - 1)
• You can only move right or down

How many unique paths are there?

Example

For a 3 × 3 grid:

S → . → .
↓   ↓   ↓
. → . → .
↓   ↓   ↓
. → . → E

Output:

6

Key Insight

To reach cell (i, j):

• You must come from above (i - 1, j)
• Or from the left (i, j - 1)

So the recurrence is:

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

DP State Definition

Let:

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

Base Cases

• First row: only one way (move right)
• First column: only one way (move down)

dp[0][j] = 1
dp[i][0] = 1

Bottom-Up DP (Tabulation)

Rust Implementation

pub fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1; n]; m];

    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    dp[m - 1][n - 1]
}

Example Usage

fn main() {
    println!("{}", unique_paths(3, 3)); // 6
    println!("{}", unique_paths(3, 7)); // 28
}

Space Optimization (1D DP)

Only the previous row is needed.

pub fn unique_paths_optimized(m: usize, n: usize) -> usize {
    let mut dp = vec![1; n];

    for _ in 1..m {
        for j in 1..n {
            dp[j] += dp[j - 1];
        }
    }

    dp[n - 1]
}

Time and Space Complexity

Time Complexity

Space Complexity

Common Variations

Grid path problems often include constraints:

• Obstacles (blocked cells)
• Minimum path sum
• Maximum path sum
• Diagonal movement allowed

All use similar DP logic with modified transitions.

Common Mistakes

• Forgetting base cases
• Out-of-bounds access
• Incorrect initialization
• Confusing row and column indices

Summary

• Grid paths are a foundational 2D DP problem
• Each cell depends on top and left neighbors
• Easy to optimize space
• Many DP problems build on this pattern