Unique Paths II

  A man is located at the top-left corner of a mxn  grid .

he can only move either down or right at any point in time. he has to reach the bottom-right corner of the grid 

How many possible unique paths are there?

An obstacle and space is marked as 1 and 0 respectively in the grid.

its better to try  Unique Paths I first , than solve this problem

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

method 2 :

using dynamic programming

c++ implementation:

int uniquePathsWithObstacles(vector<vector<int>>& g) {
        int m=g.size();
        int n=g[0].size();
        int dp[m][n];
        if(g[0][0]==1)
            return 0;
        dp[0][0]=1;
        for(int i=1;i<m;i++)
        {
            if(g[i][0]==1 ||dp[i-1][0]==0)
                dp[i][0]=0;
            else
                dp[i][0]=1;
        }
        for(int j=1;j<n;j++)
        {
            if(g[0][j]==1|| dp[0][j-1]==0)
                dp[0][j]=0;
            else
                dp[0][j]=1;
        }
        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(g[i][j]==1)
                    dp[i][j]=0;
                else
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
        
    }

Time Complexity: O(mxn) 

space Complexity: O(mxn)