Unique Paths: Grid Movement DP

Key Insights

• Grid path counting problems exhibit perfect DP properties: each cell’s path count depends only on its immediate neighbors, creating overlapping subproblems that recursive solutions wastefully recompute
• Space optimization from O(m×n) to O(n) is straightforward because each row only depends on the previous row—a pattern that applies to many 2D DP problems
• The mathematical solution using binomial coefficients is asymptotically faster but breaks down when obstacles exist, making the DP approach more versatile for real-world variations

Introduction to Grid-Based Dynamic Programming

Grid movement problems are the gateway drug to dynamic programming. They’re visual, intuitive, and map cleanly to the core DP concepts you’ll use everywhere else. The “unique paths” problem—counting ways to traverse from the top-left to bottom-right corner of a grid—strips away domain complexity and lets you focus purely on the algorithmic pattern.

This problem appears constantly in interviews, but more importantly, it teaches you to recognize DP opportunities in production code: caching expensive computations, building solutions from smaller subproblems, and trading space for time. Master this pattern, and you’ll spot it in pathfinding algorithms, text processing, and resource allocation problems.

Problem Definition and Constraints

The setup is simple: you have an m × n grid. You start at position (0, 0) and need to reach (m-1, n-1). You can only move right or down—no backtracking, no diagonal moves. Count the total number of distinct paths.

For a 3×7 grid, the answer is 28. For a 3×2 grid, it’s 3. The numbers grow quickly with grid size.

The naive approach writes itself: try every path recursively.

def unique_paths_recursive(m: int, n: int) -> int:
    """
    Naive recursive solution - DO NOT use in production.
    Time: O(2^(m+n)), Space: O(m+n) call stack
    """
    def count_paths(row: int, col: int) -> int:
        # Base case: reached destination
        if row == m - 1 and col == n - 1:
            return 1
        
        # Base case: out of bounds
        if row >= m or col >= n:
            return 0
        
        # Recursive case: sum paths from going right and going down
        return count_paths(row + 1, col) + count_paths(row, col + 1)
    
    return count_paths(0, 0)

This works for tiny grids but explodes exponentially. For a 20×20 grid, you’re looking at billions of recursive calls. The problem? We’re recalculating the same subproblems repeatedly. The path count from (5, 7) to the destination is the same whether we arrived from (4, 7) or (5, 6), but we compute it fresh each time.

Building the DP Intuition

Dynamic programming works here because the problem has two key properties:

Optimal substructure: The number of paths to any cell equals the sum of paths to the cells that can reach it. If you can only come from above or from the left, then paths_to(i, j) = paths_to(i-1, j) + paths_to(i, j-1).

Overlapping subproblems: Multiple paths converge on the same cells. Without memoization, we recompute these intersections exponentially.

The recurrence relation is clean:

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

With base cases: the first row and first column each have exactly one path (you can only go straight right or straight down to reach them).

def unique_paths_2d_dp(m: int, n: int) -> int:
    """
    2D DP table solution.
    Time: O(m×n), Space: O(m×n)
    """
    # Initialize DP table
    dp = [[0] * n for _ in range(m)]
    
    # Base case: first row - only one way to reach each cell (go right)
    for col in range(n):
        dp[0][col] = 1
    
    # Base case: first column - only one way to reach each cell (go down)
    for row in range(m):
        dp[row][0] = 1
    
    # Fill the rest of the table
    for row in range(1, m):
        for col in range(1, n):
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
    
    return dp[m - 1][n - 1]

Walk through a 3×4 grid mentally:

[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]

Each cell sums its top and left neighbors. The bottom-right cell holds our answer: 10 unique paths.

Space Optimization Techniques

The 2D solution uses O(m×n) space, but look at the access pattern: when computing row i, we only read from row i-1. We never look back further. This means we can collapse the entire table into a single row.

The trick: process left-to-right, updating in place. When we update dp[col], the value at dp[col] still holds the previous row’s value (which is “above”), and dp[col-1] holds the current row’s left neighbor (already updated this iteration).

def unique_paths_1d_dp(m: int, n: int) -> int:
    """
    Space-optimized 1D DP solution.
    Time: O(m×n), Space: O(n)
    """
    # Initialize with first row (all 1s)
    dp = [1] * n
    
    # Process remaining rows
    for row in range(1, m):
        for col in range(1, n):
            # dp[col] currently holds value from previous row (above)
            # dp[col-1] holds current row's left neighbor (already updated)
            dp[col] = dp[col] + dp[col - 1]
    
    return dp[n - 1]

This pattern—collapsing a 2D DP table to 1D when you only need the previous row—shows up constantly. Edit distance, knapsack variants, and longest common subsequence all use it. Internalize this optimization; interviewers expect it.

Handling Obstacles and Variations

Real grids have obstacles. LeetCode’s “Unique Paths II” adds blocked cells represented as 1s in an obstacle grid. The modification is straightforward: if a cell is blocked, zero paths pass through it.

def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    """
    DP solution handling obstacles.
    obstacle_grid[i][j] = 1 means cell is blocked.
    Time: O(m×n), Space: O(n)
    """
    if not obstacle_grid or obstacle_grid[0][0] == 1:
        return 0
    
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    dp = [0] * n
    dp[0] = 1  # Starting cell is reachable
    
    for row in range(m):
        for col in range(n):
            if obstacle_grid[row][col] == 1:
                # Blocked cell: no paths through here
                dp[col] = 0
            elif col > 0:
                # Add paths from left neighbor
                dp[col] = dp[col] + dp[col - 1]
            # If col == 0 and not blocked, dp[col] keeps its value from above
    
    return dp[n - 1]

The key insight: an obstacle doesn’t just block itself—it blocks all paths that would have passed through it. By setting dp[col] = 0 for obstacles, we correctly propagate this blocking effect to all downstream cells.

Other common variations include:

• Weighted paths: Instead of counting, find minimum/maximum cost paths
• Multiple destinations: Count paths to any cell in a target set
• Limited moves: Restrict total moves or moves in each direction

Each variation tweaks the recurrence but keeps the core DP structure intact.

Mathematical Alternative

Here’s the insight that unlocks a faster solution: every path from (0, 0) to (m-1, n-1) consists of exactly m-1 down moves and n-1 right moves. The total moves are m + n - 2, and we’re choosing which m-1 of them are down moves (or equivalently, which n-1 are right moves).

This is a combinatorics problem: C(m+n-2, m-1) or equivalently C(m+n-2, n-1).

def unique_paths_math(m: int, n: int) -> int:
    """
    Combinatorial solution using binomial coefficient.
    Time: O(min(m, n)), Space: O(1)
    """
    # Calculate C(m+n-2, min(m-1, n-1)) to minimize iterations
    total_moves = m + n - 2
    choose = min(m - 1, n - 1)
    
    # Calculate binomial coefficient iteratively to avoid overflow
    # C(n, k) = n! / (k! * (n-k)!)
    # We compute this as: (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1)
    result = 1
    for i in range(choose):
        result = result * (total_moves - i) // (i + 1)
    
    return result

The integer division works because we’re computing a binomial coefficient, which is always an integer. By multiplying before dividing at each step and choosing the smaller of m-1 or n-1, we minimize both iterations and intermediate value sizes.

Complexity Analysis and When to Use Each Approach

Use the mathematical approach when:

• No obstacles exist
• You need maximum performance
• Grid dimensions are large but path count fits in your integer type

Use the DP approach when:

• Obstacles or variable weights exist
• You need to reconstruct actual paths (not just count them)
• The problem has additional constraints that break the combinatorial structure

Practical tip: In interviews, start with the 2D DP solution—it’s clearer and easier to debug. Mention the 1D optimization and mathematical alternative as follow-ups. In production code, profile before optimizing; the 2D solution is often fast enough and more maintainable.

Grid DP problems train your eye for the pattern: identify the subproblem structure, write the recurrence, handle base cases, then optimize space. Once you’ve internalized this flow on unique paths, you’ll recognize it in problems that don’t look like grids at all—but structurally behave the same way.