This time, we have obstacles we can’t access.

[

[0,0,0],

[0,1,0],

[0,0,0]

]

means [1][1] is can not be stepped on.

Find the total number of possible to reach the bottom right.

# DP

We use steps to keep the numbers of ways to get to [i][j].

## Basebase case

steps[0][0] = 1 – obstacle[0][0]

So if there is an obstacle, steps[0][0] = 0

## Base case

The top row and the left column are the base case

### Row

For each entry in top row, if it’s equals to the entry to its left if the entry itself is not an obstacle.

### Column

in similar fashion

## Recurrence

It is very similar, but this time, steps[i][j] will remain zero if there is an obstacle at [i][j]

## Corner cases

```
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
std::vector<std::vector<long long>> steps(m, std::vector<long long>(n, 0));
// steps[i][j] stores num of ways to get to [i + 1][j + 1]
steps[0][0] = 1 - obstacleGrid[0][0];
for (int i = 1; i < m; i++)
if (obstacleGrid[i][0] != 1)
steps[i][0] = steps[i -1][0];
for (int i = 1; i < n; i ++)
if (obstacleGrid[0][i] != 1)
steps[0][i] = steps[0][i - 1];
for (int i = 1; i < m; i ++){
for (int j = 1; j < n; j ++){
long long top = (-obstacleGrid[i - 1][j] + 1) * steps[i - 1][j];
long long left = (1 - obstacleGrid[i][j - 1]) * steps[i][j - 1];
if (obstacleGrid[i][j] != 1)
steps[i][j] = top + left;
}
}
return steps[m - 1][n - 1];
}
```