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 代码functionuniquePathsWithObstacles(obstacleGrid:number[][]):number{constmobstacleGrid.length;constnobstacleGrid[0].length;// 起点或终点有障碍直接返回 0if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1){return0;}constdp:number[]newArray(n).fill(0);dp[0]1;for(leti0;im;i){for(letj0;jn;j){if(obstacleGrid[i][j]1){dp[j]0;}elseif(j0){dp[j]dp[j-1];}}}returndp[n-1];}复杂度分析指标 复杂度时间复杂度 O(m × n)遍历整个网格空间复杂度 O(n)使用一维滚动数组示例验证输入obstacleGrid[[0,0,0],[0,1,0],[0,0,0]]输出2路径为右 → 右 → 下 → 下下 → 下 → 右 → 右关键点起点或终点为障碍物时直接返回 0。使用一维数组滚动更新dp[j] 在更新前代表上一行的值更新后代表当前行的值。遇到障碍物时 dp[j] 0后续列不会从该位置获得路径。 DeepSeek LeetCode 63. 不同路径 II TypeScript实现
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 代码functionuniquePathsWithObstacles(obstacleGrid:number[][]):number{constmobstacleGrid.length;constnobstacleGrid[0].length;// 起点或终点有障碍直接返回 0if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1){return0;}constdp:number[]newArray(n).fill(0);dp[0]1;for(leti0;im;i){for(letj0;jn;j){if(obstacleGrid[i][j]1){dp[j]0;}elseif(j0){dp[j]dp[j-1];}}}returndp[n-1];}复杂度分析指标 复杂度时间复杂度 O(m × n)遍历整个网格空间复杂度 O(n)使用一维滚动数组示例验证输入obstacleGrid[[0,0,0],[0,1,0],[0,0,0]]输出2路径为右 → 右 → 下 → 下下 → 下 → 右 → 右关键点起点或终点为障碍物时直接返回 0。使用一维数组滚动更新dp[j] 在更新前代表上一行的值更新后代表当前行的值。遇到障碍物时 dp[j] 0后续列不会从该位置获得路径。