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];
}