刷题记录 动态规划-7: 63. 不同路径 II

题目：63. 不同路径 II

难度：中等

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 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

一、模式识别

类似于刷题记录 动态规划-5: 62. 不同路径-CSDN博客，本题我尝试过三种解法：

首先最容易想到的就是基于递归的DFS（深度优先搜索），

然后如果沿着递推公式能想到从终点返回起点这一层就能写出动态规划解法

最后代码随想录还给出了算组合数的方法（数论）

1.DFS

同样地，根据动态规划方法的递推公式可以直接写出基于递归的DFS

2.动态规划

本题属于经典动态规划问题，而且动规的很多要素题干中已经直接给出

五部曲：

1.动规数组意义：位于位置(i, j)时剩余的总步数

2.递推公式：dp(i, j) = dp(i - 1, j) + dp(i, j - 1)

解释：

机器人处于位置(i, j)时，每次只能向下或者向右移动一步两种选择，

分别可以到达(i - 1, j)和位置(i, j - 1)，

由于障碍物的存在，会有两类边界情况：

①遇见障碍物dp(i, j) = 0

②当机器人走到边缘位置(i == m - 1 or j == n - 1)，路径便只剩下一条：

边缘位置没有障碍物时，路径只剩下一条, dp(i, j) = 1

只要边缘位置有至少一个障碍物，该路径就会被堵死,

不仅时障碍物位置，整条边缘线都被堵死：dp(i, j) = 0

3.初始化：题干：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）

4.遍历顺序：本题常规，根据递推公式：

注意，dp的访问顺序和机器人的寻路顺序完全相反

5.举例：略

3.数论：算组合数

对于无障碍物的情况：

无论怎么走，从起点(m, n)到终点(1, 1)都要走m + n - 2步，

其中，横向m - 1步，纵向n - 1步

因此该问题就顺理成章的转化成了C(m + n - 2), (m - 1)的组合问题

如果有障碍物，我一开始的思路是

有障碍物总数：总数 - 起点到障碍物路数×障碍物到终点路数

但这个思路是不行的！！！我会在后面详述

二、代码实现

1.DFS

这方法很好想，而且代码简洁，

思路是顺着机器人寻路，所以可读性强，只需要把递推公式表达清楚即可

但就是有个小小的问题：会超时！

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        def helper(i, j):
            if obstacleGrid[i][j] == 1:
                return 0
            if i == m - 1 and j == n - 1:
                return 1
            if i == m - 1:
                return helper(i, j + 1)
            if j == n - 1:
                return helper(i + 1, j)
            return helper(i + 1, j) + helper(i, j + 1)
        return helper(0, 0)

问题源于其指数级的时间复杂度：O(2^(m + n - 1) - 1)

2.动态规划

注意和代码随想录不一样，

我自己写的时候二维OMN空间写法时直接用obstacleGrid充当dp数组，

所以遍历顺序反序，返回值位置是(0, 0)

（1）二维OMN空间写法

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    if i == m - 1:
                        if j < n - 1 and obstacleGrid[i][j + 1] == 0:
                            obstacleGrid[i][j] = 0
                        else:
                            obstacleGrid[i][j] = 1
                    elif j == n - 1:
                        if i < m - 1 and obstacleGrid[i + 1][j] == 0:
                            obstacleGrid[i][j] = 0
                        else:
                            obstacleGrid[i][j] = 1
                    else:
                        obstacleGrid[i][j] = obstacleGrid[i + 1][j] + obstacleGrid[i][j + 1]
        return obstacleGrid[0][0]

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)

耗时：0ms

（2）一维ON空间写法

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [1] * n
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                else:
                    if i == m - 1:
                        if j < n - 1 and dp[j + 1] == 0:
                            dp[j] = 0
                        else:
                            dp[j] = 1
                    elif j == n - 1:
                        if i < m - 1 and dp[j] == 0:
                            dp[j] = 0
                        else:
                            dp[j] = 1
                    else:
                        dp[j] += dp[j + 1]
        return dp[0]

• 时间复杂度：O(m × n)
• 空间复杂度：O(n)

耗时：0ms

可读性有点差，所以稍微解释一下，和二维空间代码的对应关系：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 和 dp[j] += dp[j - 1]

dp[i][j]: 更新后的dp[j]

dp[i - 1][j]: 更新前的dp[j]

dp[i][j - 1]: dp[j - 1]

三、为什么本题不能用算组合数的方法做？

1.欠考虑的情况

如果按照“总数 - 起点到障碍物路数×障碍物到终点路数”的思路，将写出以下代码：

class Solution:
    def calculate_conbination(self, m, n):
        num = 1
        a, b = m + n - 2, min(m - 1, n - 1)
        count = b
        while count > 0:
            num *= a
            a -= 1
            while b > 0 and num % b == 0:
                num //= b
                b -= 1
            count -= 1
        return num

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        ob = False
        x, y = 0, 0
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    x, y = i, j
                    ob = True
        return self.calculate_conbination(m, n) - (self.calculate_conbination(x + 1, y + 1) * self.calculate_conbination(m - x, n - y)) if ob else self.calculate_conbination(m, n)

然后就会这样：

输入

obstacleGrid =

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

输出

1

预期结果

0

因为障碍物可能不止一个！！！

2.改进后发现该方法只能解决某些特殊情况

那继续改进，将公式改进为：总数 - Σ起点到障碍物路数×障碍物到终点路数

然后写出这个代码：

class Solution:
    def calculate_conbination(self, m, n):
        num = 1
        a, b = m + n - 2, min(m - 1, n - 1)
        count = b
        while count > 0:
            num *= a
            a -= 1
            while b > 0 and num % b == 0:
                num //= b
                b -= 1
            count -= 1
        return num

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        obs = []
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    obs.append((i, j))
        ans = self.calculate_conbination(m, n)
        for x, y in obs:
            ans -= (self.calculate_conbination(x + 1, y + 1) * self.calculate_conbination(m - x, n - y))
        return ans

 然后就会这样：

输入

obstacleGrid =

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

输出

0

预期结果

7

为什么呢？

因为你当障碍物数量超过一个，可能有些路径被重复计算！

所以该方法只适用于障碍物数量少于等一个的情况！！！