带障碍物的不同路径数

题目描述

在一个二维网格中，你从左上角出发，每次只能向右或向下移动一格，试图到达右下角。网格中某些格子是“障碍物”，不能通过。问从左上角到右下角有多少条不同的可行路径？

输入：

• 网格用二维数组表示，其中 0 表示空单元格，1 表示障碍物。
• 网格大小为 \(m \times n\)（行数 × 列数）。

输出：

• 一个整数，表示不同路径的数量。如果无法到达，返回 0。

示例：
输入：

grid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

输出：2
解释：
两条路径：

1. 右 → 右 → 下 → 下
2. 下 → 下 → 右 → 右

解题过程

步骤 1：定义状态

设 dp[i][j] 表示从起点 (0,0) 到达格子 (i,j) 的不同路径数。

• 如果 grid[i][j] == 1，表示该格是障碍物，则 dp[i][j] = 0（不可达）。
• 否则，dp[i][j] 等于从上方或左方到达该格的路径数之和。

步骤 2：状态转移方程

如果 grid[i][j] == 0（非障碍物）：

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

如果 grid[i][j] == 1：

\[dp[i][j] = 0 \]

步骤 3：初始化

起点 (0,0) 的路径数取决于它是否是障碍物：

• 如果 grid[0][0] == 0，则 dp[0][0] = 1（只有一条路径：原地不动）。
• 如果 grid[0][0] == 1，则 dp[0][0] = 0。

对于第一行（i = 0）和第一列（j = 0）的其余格子：

• 如果当前格是障碍物，则路径数为 0。
• 否则，路径数只能来自左侧（对第一行）或上方（对第一列）。注意：如果某个格子被障碍物阻挡，其后续格子也都不可达，因为路径只能向右或向下延伸。

具体初始化方法：

1. 初始化 dp[0][0] 如上。
2. 对于第一行（j = 1 到 n-1）：
   • 如果 grid[0][j] == 0 且 dp[0][j-1] == 1，则 dp[0][j] = 1，否则为 0。
3. 对于第一列（i = 1 到 m-1）：
   • 如果 grid[i][0] == 0 且 dp[i-1][0] == 1，则 dp[i][0] = 1，否则为 0。

步骤 4：计算顺序

按行从左到右计算（或按列从上到下），确保计算 dp[i][j] 时，dp[i-1][j] 和 dp[i][j-1] 已计算。

步骤 5：最终结果

dp[m-1][n-1] 即为从起点到终点的不同路径数。

逐步计算示例

示例网格：

0 0 0
0 1 0
0 0 0

1. 初始化 dp 数组（大小 3×3）：

   • dp[0][0] = 1（起点非障碍）。

2. 第一行（i=0）：

   • j=1：grid[0][1]=0 且 dp[0][0]=1 → dp[0][1]=1
   • j=2：grid[0][2]=0 且 dp[0][1]=1 → dp[0][2]=1

3. 第一列（j=0）：

   • i=1：grid[1][0]=0 且 dp[0][0]=1 → dp[1][0]=1
   • i=2：grid[2][0]=0 且 dp[1][0]=1 → dp[2][0]=1

4. 计算其余位置：

   • i=1, j=1：grid[1][1]=1 → dp[1][1] = 0
   • i=1, j=2：grid[1][2]=0 → dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
   • i=2, j=1：grid[2][1]=0 → dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
   • i=2, j=2：grid[2][2]=0 → dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2

最终 dp[2][2] = 2，与示例一致。

边界情况与注意事项

1. 如果起点或终点是障碍物，直接返回 0。
2. 只需一个二维数组存储中间结果，空间复杂度 \(O(mn)\)。可优化为 \(O(n)\) 空间（只保存当前行和上一行）。
3. 路径数可能很大，需使用合适的数据类型（如 64 位整数）。

代码框架（Python）

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return 0
    
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    
    # 第一行
    for j in range(1, n):
        if grid[0][j] == 0:
            dp[0][j] = dp[0][j-1]
    
    # 第一列
    for i in range(1, m):
        if grid[i][0] == 0:
            dp[i][0] = dp[i-1][0]
    
    # 填充其余
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]