Unique paths in a Grid with Obstacles-Using Bottom-Up DP

Using Bottom-Up DP (Tabulation) – O(m*n) Time and O(m*n) Space

Here the challenge is to determine the count of distinct paths in a grid including obstacles. The state dp[i][j] will show the count of different paths to go to the cell (i, j).

Relation in Dynamic Programming:

• Base Case: Should it be not an impediment (grid[0][0] == 0), the beginning point (0, 0) is set to 1.
• Every cell (i, j): Should the cell have an obstacle (grid[i][j] == 1), there are no pathways to this cell, so dp[i][j] = 0.
• Otherwise, should there be no barrier, we determine the number of pathways by aggregating paths from the cell above (dp[i-1, j]) and from the left (dp[i, j-1], i.e dp[i][j] = dp[i-1][j] + dp[i][j-1].
• For every cell, we so examine the cells directly to the left and above. We add a valid path found in either of those cells to the present cell.

C++

// C++ Code to find unique paths with obstacles
// using tabulation
#include <bits/stdc++.h>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int r = grid.size(), c = grid[0].size();
    
    // Initialize DP table with zeros
    vector<vector<int>> dp(r, vector<int>(c, 0));

    // Initialize starting cell if there's no obstacle
    if(grid[0][0] == 0) {
        dp[0][0] = 1;
    }

    // Fill the DP table
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
          
            // If cell has an obstacle, set paths to 0
            if(grid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
              
                // Accumulate paths from top cell
                if(i > 0) dp[i][j] += dp[i-1][j];
              
                // Accumulate paths from left cell
                if(j > 0) dp[i][j] += dp[i][j-1];
            }
        }
    }

    // Return paths count for the 
      // bottom-right cell
    return dp[r-1][c-1];
}

int main() {
  
    vector<vector<int>> grid = { { 0, 0, 0 },
                                 { 0, 1, 0 },
                                 { 0, 0, 0 } };

    cout << uniquePathsWithObstacles(grid);
}

Java

// Java Code to find unique paths with obstacles
// using tabulation
class GfG {

    static int uniquePathsWithObstacles(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        
        // Initialize DP table with zeros
        int[][] dp = new int[r][c];

        // Initialize starting cell if 
          // there's no obstacle
        if(grid[0][0] == 0) {
            dp[0][0] = 1;
        }

        // Fill the DP table
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
              
                // If cell has an obstacle, set
                  // paths to 0
                if(grid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                  
                    // Accumulate paths from top cell
                    if(i > 0) dp[i][j] += dp[i-1][j];
                  
                    // Accumulate paths from left cell
                    if(j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }

        // Return paths count for the 
          // bottom-right cell
        return dp[r-1][c-1];
    }

    public static void main(String[] args) {
      
        int[][] grid = { { 0, 0, 0 },
                         { 0, 1, 0 },
                         { 0, 0, 0 } };

        System.out.println(uniquePathsWithObstacles(grid));
    }
}

Python

# Python code to find unique paths with 
# obstacles using space optimization

def uniquePathsWithObstacles(grid):
    r, c = len(grid), len(grid[0])

    # Initialize DP array with zeros
    dp = [0] * c

    # Set the starting cell if there's
    # no obstacle
    dp[0] = 1 if grid[0][0] == 0 else 0

    # Fill the DP array for each row
    for i in range(r):
        for j in range(c):
          
            # If there's an obstacle, 
            # set dp[j] to 0
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
              
                # Add the value from the
                # left cell
                dp[j] += dp[j - 1]

    # Return paths count for the 
    # bottom-right cell
    return dp[c - 1]

if __name__ == "__main__":
  
    grid = [[0, 0, 0],
            [0, 1, 0],
            [0, 0, 0]]

    print(uniquePathsWithObstacles(grid))

C#

// C# Code to find unique paths with obstacles
// using tabulation
using System;

class GfG {

    public static int uniquePathsWithObstacles(int[,] grid) {
        int r = grid.GetLength(0), c = grid.GetLength(1);
        
        // Initialize DP table with zeros
        int[,] dp = new int[r, c];

        // Initialize starting cell if there's no
          // obstacle
        if(grid[0, 0] == 0) {
            dp[0, 0] = 1;
        }

        // Fill the DP table
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
              
                // If cell has an obstacle, set 
                  // paths to 0
                if(grid[i, j] == 1) {
                  dp[i, j] = 0;
                } 
                else {
                  
                    // Accumulate paths from top cell
                    if(i > 0) dp[i, j] += dp[i-1, j];
                  
                    // Accumulate paths from left cell
                    if(j > 0) dp[i, j] += dp[i, j-1];
                }
            }
        }

        // Return paths count for the
          // bottom-right cell
        return dp[r-1, c-1];
    }

    static void Main() {
      
        int[,] grid = { { 0, 0, 0 },
                        { 0, 1, 0 },
                        { 0, 0, 0 } };
      
        Console.WriteLine(uniquePathsWithObstacles(grid));
    }
}

Output

2