LeetCode 63. 不同路径 II TypeScript 实现

题目描述

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。网格中有障碍物，1 表示障碍物，0 表示空位。机器人试图达到网格的右下角，问总共有多少条不同的路径？

思路：动态规划 + 滚动数组

定义 dp[j] 表示到达当前行第 j 列的不同路径数。

· 若 obstacleGrid[i][j] == 1，则 dp[j] = 0（障碍物无法到达）。
· 否则，若 j > 0，则 dp[j] += dp[j - 1]（从上方和左方累加）。
· 第一列 j = 0 时，dp[0] 继承上一行的值（只能一直向下走）。

TypeScript 代码

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;

    // 起点或终点有障碍，直接返回 0
    if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
        return 0;
    }

    const dp: number[] = new Array(n).fill(0);
    dp[0] = 1;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }

    return dp[n - 1];
}

复杂度分析

指标 复杂度
时间复杂度 O(m × n)，遍历整个网格
空间复杂度 O(n)，使用一维滚动数组

示例验证

输入：

obstacleGrid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]

输出：2

路径为：

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

关键点

1. 起点或终点为障碍物时直接返回 0。
2. 使用一维数组滚动更新，dp[j] 在更新前代表上一行的值，更新后代表当前行的值。
3. 遇到障碍物时 dp[j] = 0，后续列不会从该位置获得路径。