63. 不同路径 II

【题目】

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

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

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

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

示例 1：

示例 1.png

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

示例 2：

示例 2.png

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

提示：

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

【题目解析】

解题方法

这个问题是典型的动态规划问题，其核心思想在于如何处理网格中的障碍物。我们创建一个与原网格大小相同的动态规划表dp，其中dp[i][j]表示到达[i,j]位置的路径数。关键步骤如下：

1. 初始化：初始化dp数组的第一行和第一列。如果遇到障碍物（即obstacleGrid[i][j] == 1），则该位置及其后面的位置均不可达，dp值为0。
2. 状态转移：对于dp表中的每一个位置，如果该位置有障碍物，则到达该位置的路径数为0；如果没有障碍物，则当前位置的路径数等于其上方和左方两个位置的dp值之和。
3. 返回结果：最后，dp[m-1][n-1]即为到达网格右下角的路径总数。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        
        # 初始化第一列
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
            
        # 初始化第一行
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1
        
        # 填充dp表
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]

执行效率

image.png

【总结】

适用问题类型

• 问题类别：动态规划适用于多种问题类型，特别是可分解为重叠子问题的情况。"不同路径 II"问题，考虑网格中障碍物的存在，是动态规划在计数问题中的一种应用。
• 示例问题："不同路径 II"挑战在于计算从网格左上角到右下角，绕过障碍物的所有可能路径数量。

解决算法：动态规划

• 算法核心：动态规划算法通过构建DP表（一般是二维数组）保存解决过的子问题的解，避免重复计算。该方法清晰定义了状态、状态转移方程、初始状态和边界条件，为问题提供系统化解决框架。
• 系统框架：动态规划为解决包含障碍物的路径问题提供了一种系统化求解方法，通过逐步构建解空间来达到最终解。

时间复杂度与空间复杂度

• 时间复杂度：O(m*n)，其中m和n分别代表网格的行和列数。这是因为算法需要遍历整个网格来为每个单元格计算到达它的路径数。
• 空间复杂度：O(m*n)，主要空间开销来源于存储每个单元格到达路径数的DP表。通过状态压缩，可以在特定条件下将空间复杂度降至O(n)或O(m)。

实践意义

• 广泛应用：动态规划算法不仅适用于"不同路径 II"这类路径计数问题，还广泛应用于字符串处理、背包问题等多种复杂问题的解决，对提升编程和问题解决能力有显著帮助。
• 优化与应用：通过优化计算过程，动态规划算法不仅提升了执行效率，也增强了对复杂问题的处理能力，是算法学习和应用中的关键技能之一。

总结而言，动态规划方法对于解决"不同路径 II"中考虑障碍物的路径计数问题展现出了明显优势，通过减少重复计算并系统地构建解空间，显著提高了问题解决的效率和可行性。

题目链接

不同路径 II