题目
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
答案
在Unique Paths的基础上，只需要当遇到obstacle的时候将dp[i][j]设为0即可
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[m - 1][n - 1] = 1;
for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
int right_paths = 0, down_paths = 0;
// Obstacle grid
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
// Skip finish grid
if(i == m - 1 && j == n - 1) continue;
// right
if(j < n - 1)
right_paths = dp[i][j + 1];
// down
if(i < m - 1)
down_paths = dp[i + 1][j];
dp[i][j] = right_paths + down_paths;
}
}
return dp[0][0];
}
}
