Unique paths in a Grid with Obstacles-Using Top-Down DP

/ DSA / By
Spread the love
Skylinewebz

Using Top-Down DP(Memoization) – O(m*n) Time and O(m*n) Space

  1. Ideal Framework
    Smaller subproblems help one to identify original pathways from (0, 0) to (r-1, c-1). Specifically, we require the outcomes of two smaller subproblems to determine the number of distinct paths to any cell (i, j):
  • There are i+1, j pathways leading to the cell below.
  • There are i, j+1 pathways to the cell to the right.
  1. Interlocking Problems
    Many subproblems are computed several times while using a recursive approach to discover the number of distinct paths in a grid with obstacles. For UniquePathHelper(i, j), for example, where i and j reflect the current cell in the grid, we could have to compute the same value several times during recursion.
  • Changing two parameters—the current row index i and the current column index j—representing the current grid position—is the recursive solution. We establish a 2D array of size r x c where r is the number of rows and c is the number of columns in the grid to track the results for every cell. I will range in value from 0 to r-1 and j from 0 to c-1.
  • We start the 2D array with -1 to signal that yet no subproblems have been computed.
  • We find whether the value at memo[i][j] is -1. If so, we then work to find the answer. otherwise we bring back the saved outcome.

C++

// C++ code to find number of unique paths
// using Memoization
#include <bits/stdc++.h>
using namespace std;

// Helper function to find unique paths 
// recursively with memoization
int UniquePathHelper(int i, int j, int r, int c, 
                     vector<vector<int>>& grid, 
                     vector<vector<int>>& memo) {

    // If out of bounds, return 0
    if(i == r || j == c) {
        return 0;
    }

    // If cell is an obstacle, return 0
    if(grid[i][j] == 1) {
        return 0;
    }

    // If reached the bottom-right cell, return 1
    if(i == r-1 && j == c-1) {
        return 1;
    }

    // If value is already computed, return it
    if(memo[i][j] != -1) {
        return memo[i][j];
    }

    // Memoize the result of recursive calls
    memo[i][j] = UniquePathHelper(i+1, j, r, c, grid, memo) + 
                 UniquePathHelper(i, j+1, r, c, grid, memo);

    return memo[i][j];
}

// Function to find unique paths with obstacles
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
  
    int r = grid.size(), c = grid[0].size();
    vector<vector<int>> memo(r, vector<int>(c, -1));
    return UniquePathHelper(0, 0, r, c, grid, memo);
}

int main() {

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

    cout << uniquePathsWithObstacles(grid);
}

Java

// Java code to find number of unique paths
// using Memoization
import java.util.*;

class GfG {

    // Helper function to find unique paths 
    // recursively with memoization
    static int UniquePathHelper(int i, int j, int r, int c, 
                                       int[][] grid, int[][] memo) {
        // If out of bounds, return 0
        if(i == r || j == c) {
            return 0;
        }

        // If cell is an obstacle, return 0
        if(grid[i][j] == 1) {
            return 0;
        }
        
        // If reached the bottom-right cell,
          // return 1
        if(i == r-1 && j == c-1) {
            return 1;
        }

        // If value is already computed, return it
        if(memo[i][j] != -1) {
            return memo[i][j];
        }

        // Memoize the result of recursive calls
        memo[i][j] = UniquePathHelper(i+1, j, r, c, grid, memo) + 
                     UniquePathHelper(i, j+1, r, c, grid, memo);

        return memo[i][j];
    }

    // Function to find unique paths with obstacles
    static int uniquePathsWithObstacles(int[][] grid) {
      
        int r = grid.length, c = grid[0].length;
        int[][] memo = new int[r][c];
        for (int[] row : memo) Arrays.fill(row, -1);
        return UniquePathHelper(0, 0, r, c, grid, memo);
    }

    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 number of unique paths
# using Memoization

# Helper function to find unique paths recursively 
# with memoization
def UniquePathHelper(i, j, r, c, grid, memo):
  
    # If out of bounds, return 0
    if i == r or j == c:
        return 0

    # If cell is an obstacle, return 0
    if grid[i][j] == 1:
        return 0
    
    # If reached the bottom-right cell, return 1
    if i == r-1 and j == c-1:
        return 1

    # If value is already computed, return it
    if (i, j) in memo:
        return memo[(i, j)]

    # Memoize the result of recursive calls
    memo[(i, j)] = UniquePathHelper(i+1, j, r, c, grid, memo) + \
                   UniquePathHelper(i, j+1, r, c, grid, memo)
    
    return memo[(i, j)]

# Function to find unique paths with obstacles
def uniquePathsWithObstacles(grid):
    r, c = len(grid), len(grid[0])
    memo = {}  
    return UniquePathHelper(0, 0, r, c, grid, memo)

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

  print(uniquePathsWithObstacles(grid))

C#

// C# code to find number of unique paths
// using Memoization
using System;
using System.Collections.Generic;

class GfG {

    // Helper function to find unique paths 
    // recursively with memoization
    static int UniquePathHelper(int i, int j,
                      int r, int c, int[,] grid, int[,] memo) {
      
        // If out of bounds, return 0
        if(i == r || j == c) {
            return 0;
        }

        // If cell is an obstacle, return 0
        if(grid[i, j] == 1) {
            return 0;
        }
        
        // If reached the bottom-right cell, return 1
        if(i == r-1 && j == c-1) {
            return 1;
        }

        // If value is already computed, return it
        if(memo[i, j] != -1) {
            return memo[i, j];
        }

        // Memoize the result of recursive calls
        memo[i, j] = UniquePathHelper(i+1, j, r, c, grid, memo) + 
                     UniquePathHelper(i, j+1, r, c, grid, memo);

        return memo[i, j];
    }

    // Function to find unique paths with obstacles
    static int uniquePathsWithObstacles(int[,] grid) {
        int r = grid.GetLength(0), c = grid.GetLength(1);
        int[,] memo = new int[r, c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                memo[i, j] = -1;
            }
        }
        return UniquePathHelper(0, 0, r, c, grid, memo);
    }

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

        Console.WriteLine(uniquePathsWithObstacles(grid));
    }
}

JS

// Javascript code to find number of unique paths
// using Memoization

// Helper function to find unique paths 
// recursively with memoization
function UniquePathHelper(i, j, r, c, grid, memo) {

    // If out of bounds, return 0
    if (i === r || j === c) {
        return 0;
    }

    // If cell is an obstacle, return 0
    if (grid[i][j] === 1) {
        return 0;
    }
    
    // If reached the bottom-right cell, return 1
    if (i === r-1 && j === c-1) {
        return 1;
    }

    // If value is already computed, return it
    if (memo[i][j] !== -1) {
        return memo[i][j];
    }

    // Memoize the result of recursive calls
    memo[i][j] = UniquePathHelper(i+1, j, r, c, grid, memo) + 
                 UniquePathHelper(i, j+1, r, c, grid, memo);

    return memo[i][j];
}

// Function to find unique paths with obstacles
function uniquePathsWithObstacles(grid) {

    let r = grid.length, c = grid[0].length;
    let memo = Array.from({ length: r },
                   () => Array(c).fill(-1));
                   
    return UniquePathHelper(0, 0, r, c, grid, memo);
}

const grid = [[0, 0, 0],
              [0, 1, 0],
              [0, 0, 0]];

console.log(uniquePathsWithObstacles(grid));