DP 9. Unique Paths 2 | DP on Grid with Maze Obstacles

This chapter extends the 2D Grid Dynamic Programming framework by introducing obstacles (dead cells) into the maze. Building directly upon the foundation established in "Unique Paths 1," we analyze how a single condition change alters our base cases, recurrence relations, and code implementation across recursive, memoized, tabulated, and space-optimized approaches.

1. Problem Statement & The Core Challenge

We are given an $N \times M$ grid (or maze) with potential obstacles. Starting from the top-left cell (0, 0), our objective is to find the total number of unique paths to reach the bottom-right cell (N - 1, M - 1).

Key Constraints & Rules:

• Allowed Movements: From any cell (i, j), you can only move Down (i + 1, j) or Right (i, j + 1).
• Obstacles (Dead Cells): Certain cells in the grid contain a value of -1, signifying a blockage or dead end. You cannot step on or pass through a cell with value -1.
• Valid Cells: Cells with a value of 0 are open and can be visited.
• Large Outputs: Because the number of paths can grow exponentially, results must be returned modulo $10^9 + 7$ (1e9 + 7).

2. Core Mental Model & The Minor Modification

If you understood DP 8 (Unique Paths 1), this problem is a near-identical cakewalk. In Unique Paths 1, every cell was open terrain. Here, we introduce a single physical constraint: walls or hazards.

Real-Life Analogy: Navigating City Streets with Roadblocks

Imagine you are walking through a grid of city streets from your home (0, 0) to your office (N-1, M-1). Moving down and right are your standard transit rules. However, if you encounter police barricades or road construction at a specific intersection (represented by -1), that route is instantly dead. You cannot accumulate paths through that node, and any recursive branch hitting that coordinate must immediately return 0 ways.

3. Step-by-Step Recurrence Evolution

Let's adapt our function definition f(i, j) representing the number of ways to reach cell (i, j) from (0, 0) (or conversely, from (i, j) back to (0, 0) depending on direction).

Base Cases & Obstacle Checks:

1. Out-of-Bounds Check: If i < 0 or j < 0, we have fallen off the grid $\rightarrow$ return 0.
2. Obstacle Check: If matrix[i][j] == -1, we have hit a dead cell $\rightarrow$ return 0.
3. Destination / Start Check: If i == 0 and j == 0, we have successfully reached the start $\rightarrow$ return 1.

int countPaths(int i, int j, vector<vector<int>>& matrix) {
    // Base Case 1: Out of bounds
    if (i < 0 || j < 0) return 0;
    
    // Base Case 2: Encountered an obstacle
    if (matrix[i][j] == -1) return 0;
    
    // Base Case 3: Reached the origin
    if (i == 0 && j == 0) return 1;
    
    int up = countPaths(i - 1, j, matrix);
    int left = countPaths(i, j - 1, matrix);
    
    return (up + left) % MOD;
}

4. Memoization Approach (Top-Down DP)

To prevent overlapping subproblems and avoid exponential time complexity $O(2^{N \times M})$, we store computed states in a 2D dp table initialized to -1.

Memoized Code Structure:

class Solution {
    int MOD = 1e9 + 7;
    
    long long helper(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& dp) {
        // 1. Out of bounds
        if (i < 0 || j < 0) return 0;
        
        // 2. Obstacle check
        if (matrix[i][j] == -1) return 0;
        
        // 3. Reached start
        if (i == 0 && j == 0) return 1;
        
        // 4. Return if already calculated
        if (dp[i][j] != -1) return dp[i][j];
        
        long long up = helper(i - 1, j, matrix, dp);
        long long left = helper(i, j - 1, matrix, dp);
        
        return dp[i][j] = (up + left) % MOD;
    }

public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return helper(n - 1, m - 1, obstacleGrid, dp);
    }
};

Note: While memoization works conceptually, deep recursion stacks on large grids can trigger Time Limit Exceeded (TLE) or Stack Overflow errors. This makes the Tabulation (Iterative) approach much safer for production environments.

5. Tabulation Approach (Bottom-Up DP)

In tabulation, we convert the top-down recursive flow into an iterative nested loop spanning from i = 0 to n - 1 and j = 0 to m - 1.

Tabulated Implementation:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int MOD = 1e9 + 7;
        
        vector<vector<int>> dp(n, vector<int>(m, 0));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // If cell is an obstacle, 0 ways through it
                if (matrix[i][j] == -1) {
                    dp[i][j] = 0;
                }
                // Base case: start cell
                else if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                } 
                else {
                    long long up = 0;
                    long long left = 0;
                    
                    if (i > 0) up = dp[i - 1][j];
                    if (j > 0) left = dp[i][j - 1];
                    
                    dp[i][j] = (up + left) % MOD;
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

6. Space Optimization Technique

Notice that when calculating the current row dp[i][j], we only ever reference values from the immediate previous row (dp[i-1][j]) and the current row's left column (dp[i][j-1]).

We can compress our 2D grid storage (O(N × M)) down to a 1D vector representing just a single row (O(M)).

Space-Optimized Code:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int MOD = 1e9 + 7;
        
        vector<int> prev(m, 0);
        
        for (int i = 0; i < n; i++) {
            vector<int> curr(m, 0);
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == -1) {
                    curr[j] = 0;
                } 
                else if (i == 0 && j == 0) {
                    curr[j] = 1;
                } 
                else {
                    long long up = 0;
                    long long left = 0;
                    
                    if (i > 0) up = prev[j];          // Value from previous row
                    if (j > 0) left = curr[j - 1];      // Value from current row, left col
                    
                    curr[j] = (up + left) % MOD;
                }
            }
            prev = curr; // Shift current row to previous for the next iteration
        }
        return prev[m - 1];
    }
};

7. Complexity Analysis Summary

The table below summarizes the performance metrics across all four implementation strategies discussed in the lecture:

Summary and Key Takeaways

• Obstacle Handling: Treating dead cells (-1) simply requires setting their path contribution to 0 across recursive base cases and iterative table updates.
• Incremental Logic: This problem builds directly on Unique Paths 1, requiring only a single additional conditional check for obstacles.
• Modulo Arithmetic: Because path counts expand rapidly, always apply % 1000000007 (1e9 + 7) upon additions to prevent integer overflow.
• Recursive to Iterative: Transitioning from memoization to tabulation avoids system stack limits on massive grid dimensions.
• Space Reduction: Recognizing that state transitions depend exclusively on the previous row allows reducing space complexity from $O(N \times M)$ to $O(M)$.