LeetCode 63. 不同路径 II（中）

61题的改进版，需要先对第一行和第一列做处理，然后再进行动态规划。

Snipaste_2020-03-17_13-28-22.png

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

Snipaste_2020-03-17_13-28-22.png

网格中的障碍物和空位置分别用 1 和 0 来表示。
说明： m 和 n 的值均不超过 100。

示例

示例 1: 

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

考察知识点

动态规划、数组

核心思想

思路和第62题类似
不过出现了障碍，且机器人只可以向下和向右移动，因此第一行的格子只能从左边的格子移动到，第一列的格子只能从上方的格子移动到。
在62题中，默认第一行和第一列都是1，但是这一题第一行和第一列可能出现障碍，所以先处理第一行和第一列的情况。
第一行、第一列处理之前

8aafa0b433830e1c1e26e5478ffed7d9c3f1f46ab0f666bdc95380a81a0fd59d-image.png

第一行、第一列处理之后

667f5142f47d976541bb9b3083708415323b36c26796141a2c35bc5d6c2664ac-image.png

处理之后的步骤就和62题一样了

Python版本

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n = len(obstacleGrid)  # n为行
        m = len(obstacleGrid[0])  # m为列
        if n == 0 or m == 0 or obstacleGrid[0][0] == 1:
            return 0
        dp = [[0 for _ in range(m)] for _ in range(n)]
        dp[0][0] = 1
        # 处理第一行的m个位置
        for j in range(1, m):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break  # 后面的位置就去不了啦
        # 处理第一列的n个位置
        for i in range(1, n):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break  # 后面的位置就去不了啦
        # 后续操作和61题一样
        for i in range(1, n):
            for j in range(1, m):
                if obstacleGrid[i][j] == 1:  # 此路不通  
                    continue
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[-1][-1]


print("leet code accept!!!")
Input = [
    [
        [0,0,0],
        [0,1,0],
        [0,0,0]
    ],
    [[1]],
    [[1,0]]
]
Input1 = [2, 3]
Answer = [2, 0, 0]


if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.uniquePathsWithObstacles(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(m \times n)\)
空间复杂度：\(O(m \times n)\) 使用了额外的dp矩阵 执行用时 :52 ms, 在所有 Python3 提交中击败了49.39%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.03%的用户

  • 改进版本，利用 obstacleGrid 作为 DP 数组，因此不需要额外的空间。
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
30
31
32
33
34
35
36
37
38
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # If the starting cell has an obstacle, then simply return as there would be
        # no paths to the destination.
        if obstacleGrid[0][0] == 1:
            return 0

        # Number of ways of reaching the starting cell = 1.
        obstacleGrid[0][0] = 1

        # Filling the values for the first column
        for i in range(1,m):
            obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)

        # Filling the values for the first row        
        for j in range(1, n):
            obstacleGrid[0][j] = int(obstacleGrid[0][j] == 0 and obstacleGrid[0][j-1] == 1)

        # Starting from cell(1,1) fill up the values
        # No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
        # i.e. From above and left.
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0

        # Return value stored in rightmost bottommost cell. That is the destination.            
        return obstacleGrid[m-1][n-1]

时间复杂度 ： \(O(M \times N)O(M×N)\) 。长方形网格的大小是 \(M \times N\)，而访问每个格点恰好一次。
空间复杂度 ： \(O(1)\)。我们利用 obstacleGrid 作为 DP 数组，因此不需要额外的空间。
执行用时 :44 ms, 在所有 Python3 提交中击败了78.39%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.03%的用户

参考连接

力扣（LeetCode）