LeetCode 62 & 63：不同路径 I & II（含障碍物）

📌 题目列表

题号	题目名称	难度
62	不同路径（Unique Paths）	中等
63	不同路径 II（Unique 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 (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

---

✅ 有障碍物版本（63）

• 遇到障碍物后，后面的格子不可达
• 一旦中断，直接 break

for (int i = 0; i < m; i++) {
    if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
    else break;
}

---

四、障碍物处理（63 题重点）

if (obstacleGrid[i][j] == 0) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
}

✅ 遇到障碍物不做处理，只处理可走位置
✅ 障碍物格子路径数为 0
✅ 不参与状态转移

---

✅ AC 代码（Java）

---

✅ 62. 不同路径（无障碍）

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[105][105];

        // 初始化第一行、第一列
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;

        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

---

✅ 63. 不同路径 II（含障碍物）

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // 起点或终点有障碍
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;

        int[][] dp = new int[m][n];

        // 初始化第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
            else break;
        }

        // 初始化第一行
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 0) dp[0][j] = 1;
            else break;
        }

        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

---

⏱️ 复杂度分析

指标	复杂度
时间复杂度	O(m × n)
空间复杂度	O(m × n)（可优化为一维 DP）

---

🔍 两题对比总结

对比项	62 题	63 题
是否有障碍	❌	✅
初始化	全 1	遇障碍中断
状态转移	完全相同	增加障碍判断
难点	理解 DP	边界 + 障碍

---

✅ 一句话总结

62 题是基础二维 DP，63 题是它的“边界 + 条件增强版”，核心仍然是 dp[i][j] = dp[i-1][j] + dp[i][j-1]。