You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

&nbsp;
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 -&gt; Right -&gt; Down -&gt; Down
2. Down -&gt; Down -&gt; Right -&gt; Right


Example 2:

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


&nbsp;
Constraints:


	m == obstacleGrid.length
	n == obstacleGrid[i].length
	1 &lt;= m, n &lt;= 100
	obstacleGrid[i][j] is 0 or 1.


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        def valid(r,c,matrix):
            return r >= 0 and c >= 0 and r < len(matrix) and c < len(matrix[0])

        dp = [[0] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]
        dp[0][0] = 1 ^ obstacleGrid[0][0]

        for r in range(len(obstacleGrid)):
            for c in range(len(obstacleGrid[0])):
                if obstacleGrid[r][c] != 1:
                    if valid(r-1, c, dp) and obstacleGrid[r-1][c] != 1:
                        dp[r][c] += dp[r-1][c]
                    if valid(r, c-1, dp) and obstacleGrid[r][c-1] != 1:
                        dp[r][c] += dp[r][c-1]

        return dp[-1][-1]
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] path = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
			//if there is an obstacle at the current block then you cannot get there
                if(obstacleGrid[i][j]!=1){
                    if(i==0 && j==0)
                        path[i][j] = 1;
                    if(i>0)
                        path[i][j] += path[i-1][j];
                    if(j>0)
                        path[i][j] += path[i][j-1];
                }
            }
        }
        return path[--m][--n];
    }
}
class Solution {
public:
    int dp[101][101];
    int paths(int i,int j,int &m, int &n,vector<vector<int>> &grid){
        if(i>=m || j>=n) return 0;
        
        if(grid[i][j] == 1) return 0;
        
        if(i== m-1 && j== n-1) return 1;
        
        if(dp[i][j] != -1) return dp[i][j];
        
        int v = paths(i,j+1,m,n,grid);
        int h = paths(i+1,j,m,n,grid);
        
        return dp[i][j] = v + h;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        memset(dp,-1,sizeof(dp));
        
        return paths(0,0,m,n,obstacleGrid);
    }
};
var uniquePathsWithObstacles = function(grid) {
        let m=grid.length, n=grid[0].length;
        const dp = [...Array(m+1)].map((e) => Array(n+1).fill(0));
        dp[0][1]=1;
        for(let i=1;i<m+1;i++){
            for(let j=1;j<n+1;j++){
                dp[i][j]=grid[i-1][j-1]==1 ? 0:dp[i][j-1]+dp[i-1][j]; 
            }
        }
        return dp[m][n];
};
Unique Paths II