Unique Paths II - 2D Dynamic Programming

Note:

Before attempting this question it is highly recommended to try Unique Paths which would give you a better understanding of this question.

My approach:

Everything is the same as the Unique Path question except there is one more base case or condition added.

This is a question where we have a fixed starting point and a fixed ending point. We will have to use recursion.

We will have to use an extra space for a 2D array for both Memoization and dynamic programming.

My solution:

• Recursive

• Iterative

Code:

• Memoization

class Solution {
public:

    int helper(vector<vector<int>>& obstacleGrid, int n, int m, int i, int j,vector<vector<int>>& dp){

        if(i>=n || j>=m){
            return 0;
        }

        if(obstacleGrid[i][j]==1){
            return 0;
        }

        if(i==n-1 && j==m-1){
            return 1;
        }

        if(dp[i][j]!=-1){
            return dp[i][j];
        }

        int down = helper(obstacleGrid,n,m,i+1,j,dp);
        int right = helper(obstacleGrid,n,m,i,j+1,dp);

        dp[i][j] = down+right;
        return down+right;
    }

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();

        if(obstacleGrid[n-1][m-1]==1){
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(m,-1));
        return helper(obstacleGrid,n,m,0,0,dp);
    }
};

• Dynamic Programming

class Solution {
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));

        dp[0][0] = !obstacleGrid[0][0];  
        //  if the value of obstacleGrid[0][0] is 1 then there will be no paths. but if it is zero then negation of zero which is 1 will be stored dp[0][0]

        for(int i=1;i<m;i++){
            if(obstacleGrid[0][i]!=1){
                dp[0][i] = dp[0][i-1];
            }else{
                dp[0][i] = 0;
            }   
        }

        for(int i=1;i<n;i++){
            if(obstacleGrid[i][0]!=1){
                dp[i][0] = dp[i-1][0];
            }else{
                dp[i][0] = 0;
            }   
        }

        for(int i=1; i<n; i++){
            for(int j=1; j<m ;j++){

                if(obstacleGrid[i][j]==1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }

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

};

Question Link:

https://leetcode.com/problems/unique-paths-ii/description/