LeetCode 62 63不同路径 I II含障碍物 题目列表题号题目名称难度62不同路径Unique Paths中等63不同路径 IIUnique Paths II中等 内容概要机器人位于m × n 网格的左上角每次只能向右或向下移动一步求到达右下角的路径数。62 题无障碍物63 题部分格子有障碍物不可通行✅ 动态规划✅ 二维 DP✅ 状态转移一致✅ 面试高频题 解题思路核心一、状态定义dp[i][j]到达(i,j)的路径总数二、状态转移方程核心机器人只能从上方(i-1, j)左方(i, j-1)dp[i][j]dp[i-1][j]dp[i][j-1]三、初始化非常关键✅ 无障碍版本62第一行只能一直向右第一列只能一直向下for(inti0;im;i)dp[i][0]1;for(intj0;jn;j)dp[0][j]1;✅ 有障碍物版本63遇到障碍物后后面的格子不可达一旦中断直接breakfor(inti0;im;i){if(obstacleGrid[i][0]0)dp[i][0]1;elsebreak;}四、障碍物处理63 题重点if(obstacleGrid[i][j]0){dp[i][j]dp[i-1][j]dp[i][j-1];}✅ 遇到障碍物不做处理只处理可走位置✅ 障碍物格子路径数为0✅ 不参与状态转移✅ AC 代码Java✅ 62. 不同路径无障碍classSolution{publicintuniquePaths(intm,intn){int[][]dpnewint[105][105];// 初始化第一行、第一列for(inti0;im;i)dp[i][0]1;for(intj0;jn;j)dp[0][j]1;// 状态转移for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}}✅ 63. 不同路径 II含障碍物classSolution{publicintuniquePathsWithObstacles(int[][]obstacleGrid){intmobstacleGrid.length;intnobstacleGrid[0].length;// 起点或终点有障碍if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1)return0;int[][]dpnewint[m][n];// 初始化第一列for(inti0;im;i){if(obstacleGrid[i][0]0)dp[i][0]1;elsebreak;}// 初始化第一行for(intj0;jn;j){if(obstacleGrid[0][j]0)dp[0][j]1;elsebreak;}// 状态转移for(inti1;im;i){for(intj1;jn;j){if(obstacleGrid[i][j]0){dp[i][j]dp[i-1][j]dp[i][j-1];}}}returndp[m-1][n-1];}}⏱️ 复杂度分析指标复杂度时间复杂度O(m × n)空间复杂度O(m × n)可优化为一维 DP 两题对比总结对比项62 题63 题是否有障碍❌✅初始化全 1遇障碍中断状态转移完全相同增加障碍判断难点理解 DP边界 障碍✅ 一句话总结62 题是基础二维 DP63 题是它的“边界 条件增强版”核心仍然是dp[i][j] dp[i-1][j] dp[i][j-1]。