A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
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.
Note: m and n will be at most 100.
Example 1:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3×3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
难度：medium
题目：在 m * n 的格子左上角放置一个机器人，机器人在任何时候只能向右或向下移动，机器人尝试移动到格子的最右下角。如果在格子中加入障碍物。有多少种可能的走法？
思路：动态规划。将障碍点设置为 0。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.Memory Usage: 28.5 MB, less than 0.97% of Java online submissions for Unique Paths II.
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] > 0) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
obstacleGrid[0][0] = 1;
for (int i = 1; i < n; i++) {
obstacleGrid[0][i] = obstacleGrid[0][i] > 0 ? 0 : obstacleGrid[0][i – 1];
}
for (int i = 1; i < m; i++) {
obstacleGrid[i][0] = obstacleGrid[i][0] > 0 ? 0 : obstacleGrid[i – 1][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
obstacleGrid[i][j] = obstacleGrid[i][j] > 0 ? 0 : obstacleGrid[i – 1][j] + obstacleGrid[i][j – 1];
}
}
return obstacleGrid[m – 1][n – 1];
}
}