1. 题目在考什么两道题的核心差异1.1 “不同路径”能解决的核心场景LeetCode 62 题“不同路径”描述很简单一个机器人站在 m x n 网格的左上角每次只能向下或向右走一步问到达右下角有多少条不同路径。这道题几乎每个刷动态规划的人都会碰到原因只有一个它是理解“状态定义”和“状态转移”的最佳入门题之一。如果你按常规的力扣刷题攻略走走到热题 100 的 DP 专题时它基本是第一个挡路的。很多人在没接触 DP 之前第一反应是用 DFS 暴力搜索去数路径我刚开始也是这么干的一提交发现 m23、n12 这种组合直接超时才意识到需要把重复计算的状态缓存起来。题目的应用场景其实非常广路径规划、导航计数、棋盘走法甚至某些排列组合问题都能抽象成这个模型。别看题目简单它背后是“无后效性 最优子结构”这一整套 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(mn-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]这个方程看起来简单但要满足一个前提机器人走的是最短步数路径吗不是题目从来没有要求“最短路径”只是要求只能向右和向下移动所以所有路径的步数其实都被限制死了都是 mn-2 步。也就是说向右和向下的方向约束本身就等价于“不允许走回头路”只有前进没有后退因此每一步都只可能来自左或上。这个“前一步只有两个来源”的思维方式是整个 DP 建模的核心。以后你遇到所有网格类路径题都应该先问自己某个状态的前驱状态有哪些找到了前驱转移方程就写完了一半。2.3 初始化最容易出错边界条件我踩过的坑62 题的初始化非常固定dp[0][j] 1dp[i][0] 1。含义是沿着第一行一直往右走路径只有一条沿着第一列一直往下走路径也只有一条。但这里有个很容易被忽略的点第一行第一列的初始化顺序。如果你用双重循环从 i0 开始而不是先把边界铺好那就要单独处理 i0 或 j0 的递推逻辑。比如 62 题可以用以下两种写法写法一先铺边界再走内部代码直观但存在重复代码。写法二循环内部对 i0 和 j0 单独判断dp[i][0] 1、dp[0][j] 1然后用统一逻辑处理其他格子。这两种都可以关键是不要写出“dp[0][j1] dp[0][j] dp[-1][j]”这种越界逻辑。我第一次用 63 题的坑就是这套代码教训得来的。63 题的初始化有更隐蔽的问题。以一个二维循环统一处理为例当 obstacleGrid[i][j] 1 时dp[i][j] 必须直接等于 0否则障碍格会从历史状态继承路径数量这会导致障碍格右侧或下方的格子多算路径数。我之前见过有人把障碍判断放在状态转移之后相当于“明明撞了墙计数还继续”结果在诸如 [[0,0],[1,1]] 这类网格上得到完全错误的答案。注意推荐统一把下标 0 的行、列都纳入二维循环从 i0、j0 开始配合 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 的复杂度对比版本时间复杂度空间复杂度适用场景62 二维 DPO(mn)O(mn)新手入门建思路62 一维 DPO(mn)O(n)常规最优解63 二维 DPO(mn)O(mn)题目只要求解逻辑直观63 一维 DPO(mn)O(n)面试关注空间优化时时间上两道题都不可避免要遍历整个网格所以 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(mn-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、不同路径 IIILeetCode 980、以及输出路径本身回溯打印 dp 转移方向。这些题都共享同一个网格 DP 骨架差别只在于“状态里存的是路径数、代价最大值还是方案数”。我在实际刷题过程中发现很多人不是不会转移方程而是面对相似套路时不够敏感。看到“网格”“只能向右向下”“计数/最大值”第一反应就应该是往这个 DP 模型上靠。63 题除了积累障碍处理经验还有一个价值让你知道 DP 初始化并不是一成不变的。62 题边界全填 1是因为第一行第一列没有阻挡63 题里第一行一旦遇到障碍后续就全是 0因为机器人根本绕不开一条直线上的阻挡。如果你能把这个逻辑用大白话讲给面试官听比干巴巴背递推公式更显功底。最后分享一个我刷这两题的体会不要急着把答案调过去就完事。试着把二维代码改成一维再试着让一维代码同时兼容 62 和 63最后再问自己“如果地图特别大m、n 其中有 10^5还有没有别的办法”。这种追问式刷法才是一道经典题能带来的最大收益。
