63. 不同路径 II

题目描述

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

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

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

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

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

解法一：动态规划

如下代码解答错误，不能通过测试用例 [[0], [1]]，预期结果为 0，实际结果为 1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    h, w := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([]int, w)
    for i := 0; i < w; i++ {
        if obstacleGrid[0][i] == 1 {
            for i < w {
                dp[i] = 0
                i++
            }
            break
        }
        dp[i] = 1
    }
    for i := 1; i < h; i++ {
        for j := 1; j < w; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0
            } else {
                dp[j] += dp[j-1]
            }
        }
    }
    return dp[w-1]
}

正确代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    h, w := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([]int, w)
    for i := 0; i < w; i++ {
        if obstacleGrid[0][i] == 1 {
            for i < w {
                dp[i] = 0
                i++
            }
            break
        }
        dp[i] = 1
    }
    for i := 1; i < h; i++ {
        for j := 0; j < w; j++ {
            if j == 0 {
                if obstacleGrid[i][0] == 1 {
                    dp[j] = 0
                }
                // 如果当前位置不是障碍物，则 dp[j] 维持不变。
            } else if obstacleGrid[i][j] == 1 {
                dp[j] = 0
            } else {
                dp[j] += dp[j-1]
            }
        }
    }
    return dp[w-1]
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    n, m := len(obstacleGrid), len(obstacleGrid[0])
    f := make([]int, m)
    if obstacleGrid[0][0] == 0 {
        f[0] = 1
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if obstacleGrid[i][j] == 1 {
                f[j] = 0
                continue
            }
            if j - 1 >= 0 && obstacleGrid[i][j-1] == 0 {
                f[j] += f[j-1]
            }
        }
    }
    return f[len(f)-1]
}