1 题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/unique-paths-ii
2 题目示例
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
3 题目提示
m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
4 思路
这道题相对于62.不同路径 (opens new window)就是有了障碍。
第一次接触这种题目的同学可能会有点懵，这有障碍了，应该怎么算呢？
62.不同路径 (opens new window)中我们已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。 动规五部曲：
确定dp数组（dp table）以及下标的含义 dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
确定递推公式 递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] dp[i][j - 1]。
但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。 所以代码为：
代码语言：javascript复制if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
dp[i][j] = dp[i - 1][j] dp[i][j - 1];
}从递归公式dp[i][j] = dp[i - 1][j] dp[i][j - 1] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
本题是62.不同路径 (opens new window)的障碍版，整体思路大体一致。
但就算是做过62.不同路径，在做本题也会有感觉遇到障碍无从下手。
其实只要考虑到，遇到障碍dp[i][j]保持0就可以了。
也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。
本题思路采自代码随想录 链接：https://programmercarl.com/0063.不同路径II.html#思路
5 我的答案
代码语言：javascript复制class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
for (int i = 0; i < m; i ) {
if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍，后续都到不了
dp[0][i] = 1;
}
for (int i = 0; i < n; i ) {
if (obstacleGrid[i][0] == 1) break; 一旦遇到障碍，后续都到不了
dp[i][0] = 1;
}
for (int i = 1; i < n; i ) {
for (int j = 1; j < m; j ) {
if (obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i - 1][j] dp[i][j - 1];
}
}
return dp[n - 1][m - 1];
}
}
