1. 题目在考什么：两道题的核心差异

1.1 “不同路径”能解决的核心场景

LeetCode 62 题“不同路径”，描述很简单：一个机器人站在 m x n 网格的左上角，每次只能向下或向右走一步，问到达右下角有多少条不同路径。

这道题几乎每个刷动态规划的人都会碰到，原因只有一个：它是理解“状态定义”和“状态转移”的最佳入门题之一。如果你按常规的力扣刷题攻略走，走到热题 100 的 DP 专题时，它基本是第一个挡路的。很多人在没接触 DP 之前，第一反应是用 DFS 暴力搜索去数路径，我刚开始也是这么干的，一提交发现 m=23、n=12 这种组合直接超时，才意识到需要把重复计算的状态缓存起来。

题目的应用场景其实非常广：路径规划、导航计数、棋盘走法，甚至某些排列组合问题都能抽象成这个模型。别看题目简单，它背后是“无后效性 + 最优子结构”这一整套 DP 思维。你需要记住一句话：到某个格子的路径数，只可能由它上方的格子和左边的格子过来，这是整道题唯一的核心突破口，其余所有代码都是这句话的展开。

1.2 加上障碍物后问题的本质变化

63 题“不同路径 II”是 62 题的升级版，唯一的变化是网格里会出现值为 1 的障碍物，机器人不能进入障碍格。看起来只是加了一个条件，但它的坑远不止“遇到 1 就跳过”这么简单。

第一处变化是初始化逻辑不能无脑铺 1 了。62 题里第一行和第一列全部是 1，因为从起点过去只有一条直线路径，可一旦第一行中某个位置出现障碍，那么这个障碍右边的所有格子都不可能再到达。同理，第一列中某处出现障碍，它下方的格子也全部不可达。

第二处变化是一旦起点或终点本身是障碍，那么整个问题直接归零，但很多人容易在代码里漏掉起点的判断。第三处变化和空间优化相关，如果用了滚动数组，障碍格要主动清零，否则上一行遗留的数值会污染当前行。

所以说，63 题并不是 62 题那句“dp[i][j] = dp[i-1][j] + dp[i][j-1]”换个题目描述那么简单，它对边界条件和状态初始化的要求高了一个档次。很多刷题人 62 题一遍过，63 题反而反复提交，就是因为在“障碍之后断链”这一课上栽了跟头。

2. 状态设计与转移方程怎么推

2.1 为什么用动态规划而不是 DFS 或组合数

对于 62 题，理论上还有另外两种解法：DFS 记忆化搜索和组合数学。

DFS 加记忆化本质上是自顶向下的 DP，复杂度同样是 O(mn)，如果你递归写得熟练，用它作为备选方案没关系。但纯 DFS 不加缓存会爆炸，因为 f(m, n) 会被反复计算，复杂度接近指数级，LeetCode 第 62 题对大 m、n 专门卡这种写法。

组合数学的方法也很巧妙：机器人从左上角走到右下角，总共需要走 m + n - 2 步，其中必须有 m - 1 步是向下，问题就变成了在 m + n - 2 步中选择哪 m - 1 步向下，即 C(m+n-2, m-1)。这个解法对 62 题非常优雅，时间复杂度 O(min(m,n))，空间 O(1)。但一旦进入 63 题，网格中出现障碍后，路径总数等于总路径数减去经过至少一个障碍的路径数，而多个障碍会带来重复计数，需要容斥原理处理，障碍一多复杂度急剧上升。除非题目明确求的是无障碍网格，否则组合数不通用。

动态规划的优势在于：无论有没有障碍，转移框架都不需要大改。状态定义、转移方程维持原样，只要在取数时判断障碍格并把它的路径数置为 0 即可。这种稳定性和可扩展性，才是面试时最看重的。所以我一直建议做题时优先考虑 DP 视角，哪怕题目可以巧解，也先把动态规划实现出来。

2.2 定义 dp 数组并推导状态转移

设 dp[i][j] 表示从起点 (0,0) 走到网格第 i 行第 j 列的格子时的路径总数。这里的行、列从 0 开始计数，对应二维数组的下标。

机器人只能向右或向下走，反过来说，能到达 (i,j) 这个格子的前一步只有两种可能：从上方 (i-1,j) 下来，或者从左方 (i,j-1) 过来。因此状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

这个方程看起来简单，但要满足一个前提：机器人走的是最短步数路径吗？不是，题目从来没有要求“最短路径”，只是要求只能向右和向下移动，所以所有路径的步数其实都被限制死了，都是 m+n-2 步。也就是说，向右和向下的方向约束本身就等价于“不允许走回头路”，只有前进没有后退，因此每一步都只可能来自左或上。

这个“前一步只有两个来源”的思维方式，是整个 DP 建模的核心。以后你遇到所有网格类路径题，都应该先问自己：某个状态的前驱状态有哪些？找到了前驱，转移方程就写完了一半。

2.3 初始化最容易出错：边界条件我踩过的坑

62 题的初始化非常固定：dp[0][j] = 1，dp[i][0] = 1。含义是：沿着第一行一直往右走，路径只有一条；沿着第一列一直往下走，路径也只有一条。

但这里有个很容易被忽略的点：第一行第一列的初始化顺序。如果你用双重循环从 i=0 开始，而不是先把边界铺好，那就要单独处理 i==0 或 j==0 的递推逻辑。比如 62 题可以用以下两种写法：

写法一：先铺边界再走内部，代码直观，但存在重复代码。

写法二：循环内部对 i==0 和 j==0 单独判断，dp[i][0] = 1、dp[0][j] = 1，然后用统一逻辑处理其他格子。

这两种都可以，关键是不要写出“dp[0][j+1] = dp[0][j] + dp[-1][j]”这种越界逻辑。我第一次用 63 题的坑就是这套代码教训得来的。

63 题的初始化有更隐蔽的问题。以一个二维循环统一处理为例，当 obstacleGrid[i][j] == 1 时，dp[i][j] 必须直接等于 0，否则障碍格会从历史状态继承路径数量，这会导致障碍格右侧或下方的格子多算路径数。我之前见过有人把障碍判断放在状态转移之后，相当于“明明撞了墙，计数还继续”，结果在诸如 [[0,0],[1,1]] 这类网格上得到完全错误的答案。

注意：推荐统一把下标 0 的行、列都纳入二维循环，从 i=0、j=0 开始，配合 if 判断来处理边界。这样起点、障碍、普通格三类情况能一次处理完，不容易漏。

3. 完整实现与空间优化

3.1 用一份二维代码同时解决 62 和 63

先看一个可以直接通过 62 题的二维 DP 实现，用 Java 写：

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }

再看 63 题的标准解法，我建议起点、障碍判断都放在统一的循环里处理：

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0; } else if (i == 0 && j == 0) { dp[i][j] = 1; } else if (i == 0) { dp[i][j] = dp[i][j - 1]; } else if (j == 0) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }

这里的关键点在于：遇到障碍格时 dp[i][j] = 0，然后继续循环。为什么？因为障碍格是不可达的，它不能给任何后续格子贡献路径数，但网格中有些格子依然能通过其他方向绕过去，所以不能因为障碍存在就终止整个循环。正确逻辑是让路径在障碍之后“断链”，而不是把整个地图判死。

3.2 二维到一维的压缩思路

很多人在写完二维 DP 后会忽略一个事实：计算 dp[i][j] 只需要当前行和上一行的值。更准确地说，dp[i-1][j] 是当前列上一行的值，dp[i][j-1] 是同一行左边一格已经算出的值。

如果我们只用一维数组 dp[j] 表示“当前这一行第 j 列的值”，在遍历到第 i 行时，dp[j] 还是上一行第 j 列的旧值，dp[j-1] 已经是当前行更新后的值。于是状态转移方程可以写成：

dp[j] = dp[j] + dp[j-1]

这里的 dp[j] 等价于二维写法里的 dp[i-1][j]，dp[j-1] 等价于 dp[i][j-1]。很多人第一次看到这个表达式会愣住：同一个数组怎么两个值含义不同？原因就是遍历顺序：从左往右算，dp[j-1] 已经更新过，dp[j] 还没有更新。

这种空间优化的思路在算法题里很常见，尤其是网格 DP、背包问题。理解了它，你后面做 01 背包问题时，对“为什么要倒序遍历”会有更直觉的体会，因为背包问题和这在优化逻辑上是同一套手法，只是更新方向不同。

3.3 空间优化版实现：面试加分项

62 题空间优化写法：

class Solution { public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j - 1]; } } return dp[n - 1]; } }

63 题的滚动数组写法要更小心，因为每行遇到障碍物时，对应位置的 dp[j] 必须清零：

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; } else if (j > 0) { dp[j] += dp[j - 1]; } // j == 0 时，dp[0] 保留上一行值 // 如果上一行的起点不可达，dp[0] 会因障碍物被清零 } } return dp[n - 1]; } }

这里有一处值得展开：dp[0] 为什么不需要特别赋值？因为对每行第一列来说，它只能从上方到达，也就是 dp[0] 本身。如果上一行的 dp[0] 是 0，这一行也不是障碍，dp[0] 继续是 0，表示第一列在这行依然不可达，这正好符合“上方有障碍，第一列断链”的语义。

如果是 62 题，我习惯先 Arrays.fill(dp, 1) 表示第一行全是 1，再循环 m-1 行，相当于把第 0 行当成初始状态。这样省去了循环内对第一行特殊处理，代码也更直观。首次做空间优化时不建议直接背一维数组，而是先写出二维版本，再对比压缩，理解每一处的来源。我面试时如果被要求手写，一般先讲二维版本建立思路，再现场改成滚动数组，既稳妥又有加分效果。

3.3.1 62 和 63 的复杂度对比

时间上两道题都不可避免要遍历整个网格，所以 O(mn) 已经是下界，无法再优化。能优化的只有空间，这也是面试官最常追问的点。

4. 遇到过的常见问题与排查技巧

4.1 起点或终点是障碍物怎么办

如果 obstacleGrid[0][0] == 1，那么机器人一开始就站在障碍上，答案必然是 0。如果终点 obstacleGrid[m-1][n-1] == 1，终点不可达，答案同样是 0。

二维 DP 中，只要起点是障碍，dp[0][0] 会被设成 0，后面整个网格里的路径数全部从 0 开始推，答案自然正确。但有一个隐藏坑：如果你在代码里先把 dp[0][j] 全部初始化为 1 或 dp[i][0] 全部初始化为 1，再去覆盖障碍，起点障碍时你可能会写成：

// 错误示例 dp[0][0] = 1; if (obstacleGrid[0][0] == 1) return 0;

这样表面正确，但实际上掩盖了起点障碍在循环内的处理逻辑。更稳妥的做法是不做预设，让双层循环自己去判断，不要单独把 dp[0][0]=1 写在循环外。因为一旦你在循环外先赋值，循环内再遇到障碍，就出现“先写 1 后覆写 0”的先后依赖，逻辑一旦重构就容易漏。

4.2 循环顺序可以反过来吗

因为转移方向是“从上到下、从左到右”，所以二维循环中 i 从 0 到 m-1、j 从 0 到 n-1 是正确顺序。反过来先算右再算左就不行，因为 dp[i][j] 依赖左边的 dp[i][j-1]，它还没算出来。

也有些人会问：能不能先遍历列再遍历行？当然可以。

for (int j = 0; j < n; j++) { for (int i = 0; i < m; i++) { // dp[i][j] = ... } }

只要保证计算 dp[i][j] 时，dp[i-1][j] 和 dp[i][j-1] 都已经算完，两层循环的顺序是可以交换的。但你一定要在纸上画一画，确认两个前驱状态已经计算完毕。我见过一些帖子说“必须先遍历行”，这个说法不准确，正确的是“先遍历哪个维度都行，但单个维度内部的递增方向不能反”。

空间优化到一维以后，循环顺序的影响就变得敏感了。从左往右更新 dp[j] 时，等号右边的 dp[j] 还没被覆盖，代表上一行同一列的值；dp[j-1] 已被覆盖，代表当前行左侧的值。如果你把内层循环改成从右往左，那 dp[j-1] 还未更新，会导致结果出错。所以写滚动数组时，内层必须保持从左到右。

4.3 老生常谈的 int 溢出问题

62 题的返回值类型是 int，按理说题目设计的测试用例不会让 long 溢出，但 dp[i-1][j] + dp[i][j-1] 在极端值下可能超过 Integer.MAX_VALUE 吗？不会，如果 m、n 同时取到 100，路径总数约为 2.27e58，远超 int 范围。但题目实际限制并不会给到这种规模的角力，LeetCode 的用例保证答案在 int 范围内，只是中间过程可能溢出吗？也不会，因为中间状态一定小于或等于最终答案，而最终答案在 int 范围内，所以中间过程一定在 int 范围内。

这里反而是组合数学解法要注意：计算 C(m+n-2, m-1) 时，如果先算分子再算分母，中间值可能非常大，必须一边乘一边除，或者直接用 long 保存。DP 解法没有这个烦恼，它每一步都只做加法，值不会超过最终结果。

4.4 关于相关概念，我想多说一句

网上经常能看到“KMP 算法属于动态规划吗”“动态规划是不是背包问题”这类提问。KMP 的 next 数组确实有递推的味道，但它本质是字符串匹配的前缀函数思想，通常不算典型 DP。而 01 背包则是和路径计数完全不同的状态设计，但两者的共通点是都遵循“考虑前 i 个物品/格子，用 dp 存状态”。如果你能把不同路径这类基础题的状态定义吃透，再去学 01 背包时，你会发现框架很熟悉，只是状态数从二维变成一维、转移方向从累加变成取 max/min。

做 63 题时还有一个推荐训练方式：把每个格子的 dp 值打印出来看一遍。比如输入 [[0,0,0],[0,1,0],[0,0,0]]，推到中途你会看到：

1 1 1 1 0 1 1 1 2

看到第二行中间的 0 后，它右边仍然是 1，说明路径从上方绕过去了。这种可视化会让你瞬间明白“断链”的含义，而不是死记代码。凡是状态转移题，遇到卡点，先打印 dp 表往往比自己瞎猜高效得多。

4.5 从两道题扩展到整个 DP 刷题体系

如果你已经能独立把 62、63 的二维和滚动数组写法都撸出来，下一步可以做几类进阶题巩固：带权路径的最小路径和（LeetCode 64）、最大正方形（LeetCode 221）、不同路径 III（LeetCode 980）、以及输出路径本身（回溯打印 dp 转移方向）。这些题都共享同一个网格 DP 骨架，差别只在于“状态里存的是路径数、代价最大值还是方案数”。

我在实际刷题过程中发现，很多人不是不会转移方程，而是面对相似套路时不够敏感。看到“网格”“只能向右向下”“计数/最大值”，第一反应就应该是往这个 DP 模型上靠。

63 题除了积累障碍处理经验，还有一个价值：让你知道 DP 初始化并不是一成不变的。62 题边界全填 1，是因为第一行第一列没有阻挡；63 题里第一行一旦遇到障碍，后续就全是 0，因为机器人根本绕不开一条直线上的阻挡。如果你能把这个逻辑用大白话讲给面试官听，比干巴巴背递推公式更显功底。

最后分享一个我刷这两题的体会：不要急着把答案调过去就完事。试着把二维代码改成一维，再试着让一维代码同时兼容 62 和 63，最后再问自己“如果地图特别大，m、n 其中有 10^5，还有没有别的办法”。这种追问式刷法，才是一道经典题能带来的最大收益。