一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右思路： 我们考虑一下，
机器人只可以向下和向右移动，因此第一行的格子只能从左边的格子移动到，第一列的格子只能从上方的格子移动到。对于剩下的格子，可以从左边或者上方的格子移动到。如果格子上有障碍，那么我们不考虑包含这个格子的任何路径。我们从左至右、从上至下的遍历整个数组，那么在到达某个顶点之前我们就已经获得了到达前驱节点的方案数，这就变成了一个动态规划问题。
- 如果第一个格子是障碍，那就返回 0，否则我们把第一个点初始化为 1
- 然后开始从左到右，从上到下开始遍历。
- 如果某个格点初始不包含任何障碍物，就把值赋为上方和左侧两个格点方案数之和
- 如果这个点有障碍物，设值为 0 ，这可以保证不会对后面的路径产生贡献。
代码逻辑
- 去掉第一个节点为障碍物的情况，返回 0；
- 设一个一维数组 result 为 dp 矩阵，初始化第一个值为 1；
- 每一行遍历，如果该行某个节点是障碍物，那就把这个值设为 0，
- 否则，如果不是第一列，它到达该节点的路径就是当前的值加上左侧节点的值。
- 遍历下一行的时候，当前 result 的每一个元素，就是从上一行到这一行的路径。
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
const uniquePathsWithObstacles = obstacleGrid => {
if (obstacleGrid[0][0] == 1) return 0;
const row = obstacleGrid.length; // 行数
const col = obstacleGrid[0].length; // 列数
const result = Array(col).fill(0); // dp矩阵
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (i == 0 && j == 0) {
result[j] = 1;
}
if (obstacleGrid[i][j] == 1) {
result[j] = 0;
} else if (j > 0) {
result[j] += result[j - 1];
}
}
}
return result[col - 1];
};