原题链接：https://leetcode-cn.com/problems/unique-paths-ii/
解题思路：
- 在网格中的任意一点，都有向右和向下两种路径。同时它也是从上方和左方两个位置走过来的。
- 那么，任意一点的路径数量，等于从起点走到上方和左方点的数量之和。
- 第一行和第一列都只有一种路径，就是从起点一直走到底。
- 我们可以用一个二维数组，画出网格中每个点的路径数量，一直递推到终点，终点存储的就是所有的路径数量。
- 因此动态规划的状态转移方程为：
dp[i][j]=dp[i-1][j]+dp[i][j-1]。 - 如果遇到障碍物，则该位置的路径数量为0。
- 对于起始点
obstacleGrid[0][0]，如果它没有障碍物，路径为1，反之为0。 - 由于每个点的路径数量只和它左方和上方有关，因此状态转移方程可以优化为：
dp[i] = dp[i - 1] + dp[i]。
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// 创建数组，存储最新一行的状态
// 由于新位置的状态，只与它左方和上方的状态有关
// 也就是dp[j] = dp[j - 1] + dp[j]
// 因此只需要一维数组即可
let dp = new Array(obstacleGrid[0].length).fill(0)
// 起始位置如果无障碍物，路径为1，否则为0
dp[0] = obstacleGrid[0][0] ? 0 : 1
// 遍历每个网格位置，计算路径数量
for (let i = 0; i < obstacleGrid.length; i++) {
for (let j = 0; j < obstacleGrid[0].length; j++) {
// 如果遇到障碍物，当前位置无法经过，路径为0
if (obstacleGrid[i][j]) {
dp[j] = 0
} else {
// 如果当前位置没有障碍物，路径数量等于左方和上方的数量之和
// 如果j为0，dp[j - 1]为undefined，将其设置为0，方便计算
dp[j] += dp[j - 1] ?? 0
}
}
}
// 最后一个位置存储的就是最终结果
return dp[obstacleGrid[0].length - 1]
};
