# 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)