LeetCode 63. 不同路径 II

约 5 分钟
文章信息 17 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 滴滴 华为 网易 商汤 图森 面试经典 150 题
标签
数组 动态规划 矩阵
目录

题目描述

✅ 63. 不同路径 II

image-20230311180301715

image-20230311180258132

题意分析

在一个 m 行 n 列的网格里从左上角走到右下角，每一步只能向右或向下，网格中值为 1 的格子是障碍物，不能踏入，问一共有多少条不同的路径。

与第 62 题相比，唯一新增的信息就是障碍物。障碍物不是「绕一下多走几步」的问题——因为只能右和下、不能回头，一个格子被堵住就意味着所有必须经过它的路径全部消失，它的路径数是 0 而不是某个更小的正数。

约束里行列数都不超过 100，格子总数上限一万，说明一个逐格填表的二重循环足够；同时题目保证答案不超过 $2 \times 10^9$，恰好卡在 32 位有符号整数范围内，不必上 long，但也说明中间的路径数会很大，任何「枚举所有路径再计数」的思路必然超时。

边界上有三种情况值得先想清楚：起点本身就是障碍物，答案是 0；终点是障碍物，答案也是 0；网格只有一行或一列，此时路径唯一，只要路上没有障碍就是 1，有障碍就是 0。

解法：一维动态规划

核心思路

这是网格路径计数问题。若当前格不是障碍物，到达它的最后一步只可能来自上方或左方，两类路径互不重叠，因此二维状态满足：

\[f[r][c] = f[r-1][c] + f[r][c-1]\]

障碍格不能被任何路径到达，直接令其状态为 0。递推只依赖上一行同列和本行左邻，所以用一维数组 dp[col] 即可：从左到右处理 (row, col) 前，dp[col] 是上方的旧值，dp[col-1] 是左侧刚更新的新值；非障碍格执行 dp[col] += dp[col-1]，障碍格执行 dp[col] = 0。

令 dp[0] = 1 作为递推种子，其余为 0。这个初始化能让主循环自然覆盖起点、首行和首列：起点若被堵会立即清零；首行或首列一旦遇到障碍，该边界后续格也会保持为 0，无需额外分支。

解题步骤

  1. 创建长度为列数的 dp，初始化 dp[0] = 1。
  2. 按从上到下、从左到右的顺序遍历网格。
  3. 当前格是障碍物时将 dp[col] 清零；否则在 col > 0 时累加左侧状态 dp[col-1]。
  4. 扫描结束后返回 dp[cols-1]。

以 [[0,0,0],[0,1,0],[0,0,0]] 为例，三行处理后的 dp 依次是 [1,1,1]、[1,0,1]、[1,1,2]，所以答案为 2。这个过程也直观展示了障碍格清零后如何阻断后续路径。

代码实现

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int cols = obstacleGrid[0].length;
        int[] dp = new int[cols];
        dp[0] = 1;

        for (int row = 0; row < obstacleGrid.length; row++) {
            for (int col = 0; col < cols; col++) {
                if (obstacleGrid[row][col] == 1) {
                    // 障碍格不可到达，路径数必须清零。
                    dp[col] = 0;
                } else if (col > 0) {
                    dp[col] += dp[col - 1];
                }
            }
        }
        return dp[cols - 1];
    }
}

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    cols := len(obstacleGrid[0])
    dp := make([]int, cols)
    dp[0] = 1

    for row := 0; row < len(obstacleGrid); row++ {
        for col := 0; col < cols; col++ {
            if obstacleGrid[row][col] == 1 {
                // 当前格有障碍时，来自上方和左方的路径都不能进入。
                dp[col] = 0
            } else if col > 0 {
                dp[col] += dp[col-1]
            }
        }
    }
    return dp[cols-1]
}

复杂度分析

  • 时间复杂度：$O(mn)$，每个格子只处理一次。
  • 空间复杂度：$O(n)$，dp 的长度等于列数。

关键点总结

  • 状态含义始终是“到达当前格的路径数”，障碍格对应 0。
  • 一维压缩后必须从左向右更新，才能同时读到上方旧值和左侧新值。
  • dp[0] = 1 配合“障碍清零”，统一处理起点、首行和首列。
  • 面试时先写二维转移，再解释一维压缩及扫描顺序，推导会比直接背代码更完整。

易错点总结

  • 障碍格清零后仍执行累加，会让路径“穿过”障碍；[[0,0],[0,1]] 应返回 0。
  • 每行都把 dp[0] 重置为 1，会错误复活被障碍截断的第一列；第一列只应继承上方状态。
  • 从右向左更新会把 dp[col-1] 读成上一行的值，破坏转移不变量。
  • 首行或首列手动填 1 时容易漏掉障碍的后续影响，使用统一循环更稳妥。

相似题目

题目 难度 考察点
62. 不同路径 中等 本题的无障碍版本，可直接用组合数 $C_{m+n-2}^{m-1}$ 求闭式解
64. 最小路径和 中等 同样的转移骨架，但聚合方式从求和换成取最小值
120. 三角形最小路径和 中等 网格退化成三角形，每层下标范围变化，自底向上递推更省心
174. 地下城游戏 困难 必须从终点倒推，因为最优子结构在正向定义下不成立
688. 骑士在棋盘上的概率 中等 移动方向扩展到八个且带步数维度，状态多一维、结果是概率
931. 下降路径最小和 中等 每步可斜向移动，转移来源变成上一行的三个相邻列
1289. 下降路径最小和 II 困难 只禁止同列，需要维护上一行的最小值与次小值来避免平方级枚举
1301. 最大得分的路径数目 困难 同时维护最大得分与达到该得分的方案数，是路径计数与最优值的结合
1594. 矩阵的最大非负积 中等 因为负负得正，每格必须同时保存最大积与最小积两个状态
LCR 098. 不同路径 中等 与 62 题同题，练手可直接复用无障碍递推
LCR 099. 最小路径和 中等 与 64 题同题，转移的聚合方式为取最小
LCR 100. 三角形最小路径和 中等 与 120 题同题，重点在三角形边界的下标处理
剑指 Offer 47. 礼物的最大价值 中等 同样只能右和下，但聚合方式为取最大且要累加格子价值