63.不同路径II

描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2

解释：

3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

代码：

const map = [
    [0, 0],
    [1, 0]
]

function dp(map) {
    const m = map.length;
    const n = map[0].length
    // 创建一个二维数组
    const arr = new Array(m);
    for (let i = 0; i < m; i++) {
        arr[i] = new Array(n).fill(0);
    }
    // 将一个大任务拆解成小任务
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 如果是障碍，则该路结果为0
            arr[i][j] = map[i][j] ? 0 : 1;
            if (arr[i][j] !== 0) {
                if (i !== 0 && j !== 0) {
                    arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
                } else if (i > 0) {
                    // 下移
                    arr[i][j] = arr[i - 1][j]
                } else if (j > 0) {
                    // 横移
                    arr[i][j] = arr[i][j - 1]
                }
            }
        }
    }
    return arr[m - 1][n - 1]
}

分析：

[
    [0,0,0],
    [0,1,0],
    [0,0,0]
]

定义 f[i][j] 为到达位置 (i,j) 的不同路径数量。

那么 f[m-1][n-1] 就是我们最终的答案，

1. f[0][0]不一定是1，因为(0,0)也可能是障碍物
2. 边缘点只能需要考虑单边即 f[i][j] = f[i][j-1]
3. 障碍物点不允许移动，f[i][j] = f[i][j-1] + f[i-1][j]，的公式将存在区别，则有两种方式：
   1. 走单边
   2. 障碍物路径结果置为0

实际操作

1. 当前位置只能「往下」移动，即有 f[i][j] = f[i-1][j]
2. 是当前位置只能「往右」移动，即有 f[i][j] = f[i][j-1]
3. 当前位置即能「往下」也能「往右」移动，即有 f[i][j] = f[i][j-1] + f[i-1][j]

时间复杂度：O(nm) 空间复杂度：O(nm)

总结

这道题是不同路径的加强版，我们需要考虑障碍物对路径的影响