# LC63. Unique Paths II

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

[
[0,0,0],
[0,1,0],
[0,0,0]
]

means  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 = 1 – obstacle
So if there is an obstacle, steps = 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.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 = 1 - obstacleGrid;
for (int i = 1; i < m; i++)
if (obstacleGrid[i] != 1)
steps[i] = steps[i -1];
for (int i = 1; i < n; i ++)
if (obstacleGrid[i] != 1)
steps[i] = steps[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];
}
``````
Posted on Categories Leetcode