不同路径 II-LeetCode

63. 不同路径 II - Unique Paths II

🎯 问题描述（来源于LeetCode）

描述：
一个机器人位于一个 m x n 网格的左上角（起点为 (0,0)）。机器人每次只能向下或向右移动一步。
网格中可能存在障碍物，用 1 表示有障碍物，0 表示空地。
问机器人到达右下角 (m-1, n-1) 有多少条不同的路径？
如果障碍物阻挡了路径，则返回 0。

说明：

• 1 <= m, n <= 100。
• 障碍物和空地的数量任意。

示例：

• 示例 1：

输入: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出: 2
解释: 从起点到终点，中间的障碍物使得只有两条路径。

• 示例 2：

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

💻 解题思路

思路：动态规划（1‑based 数组 + 巧妙初始化）

算法步骤

1. 获取网格尺寸 m, n，创建 (m+1) x (n+1) 的 DP 数组，全部初始化为 0。
2. 设置 dp[0][1] = 1，这相当于把起点的路径数“预先放置”在 (0,1) 位置，从而在 (1,1) 处通过 dp[0][1] + dp[1][0] 自然得到 1。
3. 遍历每个格子 (i, j)（0‑based）：
   • 如果当前格子不是障碍物（obstacleGrid[i][j] == 0），则：
     dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]。
   • 否则，保持 dp[i+1][j+1] = 0（因为障碍物无法通过）。
4. 返回 dp[m][n]。

代码实现

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[0][1] = 1  # 关键初始化，使得 dp[1][1] 在第一个格子无阻碍时得到 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 0:
                    dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
        return dp[m][n]

📊 性能分析

• 时间复杂度：$O(m \times n)$，遍历所有格子一次。
• 空间复杂度：$O(m \times n)$，可优化到 $O(n)$（一维滚动数组）。

思考

该解法利用 1‑based 数组和 dp[0][1] = 1 的初始化技巧，避免了单独处理第一行和第一列的边界条件。

• 当网格的第一个格子 (0,0) 无障碍时，dp[1][1] = dp[0][1] + dp[1][0] = 1 + 0 = 1，正确得到起点路径数。
• 如果起点有障碍物，则 dp[1][1] 会在遍历中因为 obstacleGrid[0][0]==1 而保持为 0，最终结果也为 0。
  这种写法简洁优美，是处理二维 DP 边界问题的常用技巧。但要注意：dp[0][1] 的赋值仅适用于起点无障碍的情况？实际上，即使起点有障碍，dp[1][1] 也会因为不进入累加而保持 0，最终结果正确，因为起点被堵住就没有任何路径。
  此外，可以进一步优化空间为 $O(n)$，但当前代码清晰易懂，适合教学。