1. 题目拆解从无障碍版到障碍物版的本质变化先说说我做这道题的背景。LeetCode 62是不同路径的入门版一个机器人从m x n网格的左上角走到右下角每次只能向右或向下走问有多少条不同路径。那题用组合数学一个公式就能秒掉也可以用动态规划轻松解出来。到了LeetCode 63题目几乎没变只是在网格里多了一种值为1的格子——障碍物。机器人不能进入这些格子问法还是有多少条不同的路径。这两道题刷过的人会有一种很直接的感受62是经典动态规划入门模板63则是在模板上加了条件判断。但恰恰是这个看似微小的改动让很多人在笔试面试里翻了车。原因就一个障碍物位置的随机性打破了原来一马平川的递推假设。比如第0行第0列如果某个位置被障碍物堵住了那它右边的所有格子实际上都不可达了——这个逻辑在无障碍版本里根本不存在。我见过不止一个同学把62的代码改三行就交上去然后发现测试用例过不去。他们往往漏掉的就是这个障碍物阻断传播的关键逻辑。所以这篇文章我不打算只贴一份AC代码完事而是要把动态规划的状态设计、初始化细节、转移方程的推导、两种语言实现的差异、空间优化技巧以及我在实际跑代码时踩过的坑一条一条掰开来讲。题目本身难度是中等但想一次性写对需要你对DP的理解不是停留在背模板的层面。这道题适合谁看如果你是刚接触动态规划的初学者建议先花十分钟把62题的做法吃透再来读这篇如果你已经能独立AC想看看障碍物场景下的空间优化和边界处理细节这篇文章同样有值得参考的地方。接下来我从思路演进开始讲。2. 思路演进为什么动态规划依然是这道题的最优解2.1 穷举视角下的指数爆炸问题先摆一个直观的问题如果不用动态规划这道题怎么解最常见的朴素想法是用深度优先搜索从起点出发每到一个格子尝试向右和下走遇到障碍物就剪枝走到终点就计数加一。这个思路在网格规模小的时候能跑但在题目给定的m、n最大到100时纯DFS的复杂度是指数级的最坏情况下路径数量本身就会大到天文数字搜索树直接爆炸。那组合数学能不能用62题用组合数的方法很优雅从左上到右下需要走(m-1)次向下、(n-1)次向右总步数固定路径总数就是C(mn-2, m-1)。但63题有障碍物之后这条公式不能直接用因为障碍物会挡住一部分原本合法的排列组合。虽然可以用总数减去经过障碍物的路径数这种容斥思路但障碍物有多个、且存在相互遮挡关系时这个容斥逻辑会变得异常复杂写起来比动态规划还费劲。所以动态规划几乎是一个必然选择。它的核心思想其实非常朴素到达某个格子的路径数只取决于能走到它的上方和左方那两个格子的路径数之和。这个子问题最优解重叠的特性正是动态规划最擅长处理的场景。2.2 从62到63状态转移方程只多了一个条件先回忆一下62题的状态转移方程。定义dp[i][j]表示从起点到达网格中第i行第j列格子的路径数。由于机器人只能向右或向下移动那么到达(i,j)这个格子只能从(i-1,j)向下走一步或者从(i,j-1)向右走一步。于是dp[i][j] dp[i-1][j] dp[i][j-1]这个式子很干净没有任何附加条件。但到63题一旦网格里出现障碍物先要处理一个问题如果dp[i][j]这个格子本身是障碍物那它的路径数应该是0因为机器人根本站不上去。同时它也不应该向下一个格子传递任何路径数。所以状态转移方程变成如果 grid[i][j] 1障碍物dp[i][j] 0 否则dp[i][j] dp[i-1][j] dp[i][j-1]注意这里有一个隐含前提dp[i-1][j]和dp[i][j-1]在计算时已经处理过它们自身是否是障碍物的判断。也就是说路径信息在传播过程中遇到障碍物就截断了不会穿过障碍物继续传递。这正是我带大家看的第一层本质障碍物在动态规划中扮演的角色是一个阻断器它既不产生新的路径也不传递已有的路径。明白了这层逻辑后面所有的代码实现、边界处理、空间优化都是在围绕如何正确表达这个阻断逻辑展开的。3. 状态设计与初始化最容易写错的三个细节3.1 dp数组的口径路径数是到达而非经过先约定一下dp数组的口径这个不搞清楚后面全乱。很多资料里习惯用dp[i][j]表示从起点到(i,j)的路径总数我建议心里默念成到达(i,j)时可行走法数量。两者的差别在于语义当你处理障碍物时语义清晰可以帮你避免很多到底是该把障碍物格子设为0还是该跳过它不去更新的纠结。我的习惯是用二维int数组长度分别为m和n初值全部填0。之所以不填充1是因为障碍物的存在让初始化不能一刀切。如果整个网格第一行第一列都没有障碍物那dp[0][0]显然是1第一行每个格子都是1第一列同理。但一旦有障碍物这个一路铺1的逻辑就不成立了。后文我会专门讲这点。3.2 起点与终点的两种极端情况先看起点。如果grid[0][0]本身是障碍物也就是起点直接被堵死那结果没有任何悬念直接返回0。这个问题很多人在写代码时会忽略因为直觉上觉得起点怎么能是障碍物。但题目数据恰好就给了这种用例我在某个在线评测平台的自测用例里就看到过m1, n1, grid[[1]]的情况。如果代码没有对起点做单独判断而是直接进入循环dp[0][0]的赋值逻辑一旦处理不当就会输出错误结果。再看终点。如果grid[m-1][n-1]是障碍物机器人根本不可能到达终点答案也是0。这个情况实际上会被递推公式自然覆盖——因为终点是障碍物时dp[m-1][n-1]会被置为0返回值自然是0。所以终点的障碍物你不用写特殊判断但起点的障碍物必须在初始化时显式处理。我推荐的做法是先判断grid[0][0]如果是1直接返回0否则初始化dp[0][0] 1。这种前置判断不仅逻辑清晰也避免了后续在递推代码里做额外判断的复杂性。3.3 第一行与第一列的初始化不能盲目铺1这是这道题第一个大坑也是面试官最爱追问的点。在无障碍版本里第一行的每个格子只有一种走法一直向右第一列也只有一种走法一直向下所以可以全部初始化为1。但在有障碍物的版本里只能一直向右这个前提一旦被障碍物打断后面的格子就根本走不到了。举例说明。假设网格是3行3列第一行是[0, 1, 0]也就是第0行第1列有一个障碍物。那么机器人从(0,0)出发没法经过(0,1)自然也到不了(0,2)。所以dp[0][0] 1dp[0][1] 0障碍物dp[0][2] 0被障碍物阻断。如果你按盲目铺1的逻辑去初始化dp[0][2] 1那整道题就做错了错得很隐蔽因为大部分测试用例不会把障碍物放在第一行。正确的初始化写法应该带一个开关标记。对第一行从左往右遍历一旦遇到障碍物就把标记置为失效当前格和后续所有格的dp值都是0对第一列同理从上往下遍历遇到障碍物后标记失效。我见过有些精炼的代码里会省略显式的第一行第一列循环直接在主循环里用判断处理i 0或j 0但其实效果是一样的只是把初始化和递推合并了。后面我会给出完整代码两种方式我都有试过推荐初学者先用显式初始化的写法逻辑更直观不容易漏。4. Java与Python双语言实现代码逐行拆解与对比4.1 Java版本二维数组 显式初始化先看Java实现。我用的是标准的二维dp数组代码结构分三段边界判断、初始化、递推。每一段我都加了注释方便你对照上面讲的细节看。class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m obstacleGrid.length; int n obstacleGrid[0].length; // 起点或终点是障碍物直接返回0 if (obstacleGrid[0][0] 1) { return 0; } int[][] dp new int[m][n]; dp[0][0] 1; // 初始化第一列从上往下遇到障碍物之前都是1 for (int i 1; i m; i) { if (obstacleGrid[i][0] 1) { dp[i][0] 0; // 注意这里可以用break因为第一列一旦被堵后面的格子都无法到达 // 但用dp[i][0] 0并继续循环效果也一样因为后面都是0 break; } else { dp[i][0] dp[i - 1][0]; } } // 初始化第一行从左往右遇到障碍物之前都是1 for (int j 1; j n; j) { if (obstacleGrid[0][j] 1) { dp[0][j] 0; break; } else { dp[0][j] dp[0][j - 1]; } } // 递推主体 for (int i 1; i m; i) { for (int j 1; j n; j) { if (obstacleGrid[i][j] 1) { dp[i][j] 0; } else { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }这段代码里有一个我在初期容易写错的细节第一列初始化时我用了dp[i][0] dp[i - 1][0]而不是直接写成dp[i][0] 1。为什么因为一旦第一列前面出现了障碍物dp[i-1][0]就已经是0了0向后传递是合理的。直接写1的话相当于无视了障碍物的阻断效果。第一行同理用dp[0][j] dp[0][j - 1]递推而不是写死1。递推主体里的逻辑非常好理解遇到障碍物就置0没遇到就累加左和上的路径数。这里有一个隐藏的优化点——其实初始化第一行第一列和主体递推可以在同一个双层循环里完成用i 0或j 0判断即可。但那样代码可读性会差一些对于刷题阶段的同学我宁可推荐这种显式三步走。等你自己写熟了可以再合并成更精简的版本。4.2 Python版本同样的逻辑更直白Python版本在思路上和Java完全一致但代码写起来更省事。核心原因是Python的列表推导和动态类型让二维dp数组的创建和访问都更简洁。但有得必有失Python的列表嵌套如果初始化方式不对会出现浅拷贝的坑这个我会在后面的常见问题里专门讲。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m, n len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] 1: return 0 dp [[0] * n for _ in range(m)] dp[0][0] 1 # 初始化第一列 for i in range(1, m): if obstacleGrid[i][0] 1: break dp[i][0] dp[i - 1][0] # 初始化第一行 for j in range(1, n): if obstacleGrid[0][j] 1: break dp[0][j] dp[0][j - 1] # 递推主体 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[m - 1][n - 1]Python版本第一行的List[List[int]]需要你提前导入from typing import List在LeetCode的环境里这个是预置的但如果你在本地IDE里跑不导入就会报NameError。这是个很小但很真实的坑。再注意dp [[0] * n for _ in range(m)]这行。为什么不用[[0] * n] * m因为后者创建的每一行都是同一个列表对象的引用改一个格子会连锁改掉所有行的同一列位置。这是一个经典的Python坑我在给某个同学review代码时真的见过这个写法导致的诡异bug。说起来很有意思他会发现dp[0][5]被赋值之后dp[1][5]也奇迹般地变了排查半天才发现是初始化方式的问题。4.3 两种语言在边界判断上的细节差异Java和Python在这道题上的实现主体逻辑没有差别差别主要体现在两个方面。第一个是数组边界的获取方式。Java里二维数组先取行数obstacleGrid.length再取列数obstacleGrid[0].length。Python用len()函数同理。这里有个隐形的安全假设题目保证网格至少是1x1否则obstacleGrid[0]会越界。虽然LeetCode的测试用例不会出现空网格但在实际面试手写代码时如果面试官要求你写出对空输入的防御你可以在开头加一个if m 0 or n 0: return 0之类的判断。我自己在写工程代码时通常会保留这种防御逻辑但刷题时加不加都无所谓。第二个是break和continue的使用习惯。Java和Python都可以在循环里用break跳出。第一列初始化时遇到障碍物可以直接break因为第一列后续格子全部不可达。但我在最开始写的时候用的是不break、只是把当前格子置0的逻辑效果等价。这两种写法我建议你优先用break因为语义更明确一旦堵死后面没必要继续遍历。5. 空间优化从二维到一维的滚动数组思路5.1 为什么能优化观察dp递推的依赖关系如果你只看正确性前面那两段二维dp的代码已经完全够了时间复杂度O(mn)空间复杂度O(mn)题目给的数据范围m、n最大100二维数组也就1万个int内存占用微不足道。但动态规划题有一个约定俗成的加分项空间优化。尤其面试时面试官经常会追问能不能把空间复杂度降到O(n)LeetCode 63就是一道非常适合展示这个能力的题。空间优化的可行性和状态转移方程的依赖范围直接相关。看dp[i][j] dp[i-1][j] dp[i][j-1]它只依赖当前行左边一个格子同一行和上一行同一列的格子。换句话说在计算第i行时真正需要的只有第i-1行的数据再往前的行数据用了之后就再也不会被访问到。那留着一整个二维数组完全是浪费。我们可以只用一个长度为n的一维数组在遍历过程中滚动更新。5.2 一维数组的更新逻辑从左到右的奥秘一维数组的做法是dp[j]在某一轮循环中表示的是到达当前行第j列的路径数。当我们在第i行从左往右遍历时dp[j]在被更新之前保存的还是上一行第j列的数据也就是dp[i-1][j]而dp[j-1]在更新之后保存的已经是当前行第j-1列的数据也就是dp[i][j-1]。于是转移方程就变成了dp[j] dp[j]上一行的同列 dp[j-1]当前行的左边一列这个等式简直完美契合了二维dp的转移依赖。如果遍历方向反过来从右往左那就麻烦了dp[j-1]还没更新拿到的还是上上行的旧数据。所以这里从左到右的遍历方向是空间优化的关键不是随便写的。5.3 空间优化版的初始化一维数组的三种处理方式一维数组的初始化和更新比二维数组稍微绕一点但理解之后很爽。我给出一个比较通用的写法class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int n obstacleGrid[0].length; int[] dp new int[n]; // 初始化处理第一行 for (int j 0; j n; j) { if (obstacleGrid[0][j] 1) { break; // 遇到障碍物后续全部保持0 } dp[j] 1; } // 从第二行开始滚动更新 for (int i 1; i obstacleGrid.length; i) { for (int j 0; j n; j) { if (obstacleGrid[i][j] 1) { dp[j] 0; } else if (j 0) { // 第一列只能来自上方dp[0]在没有被障碍物阻断时保持不变 // 若上方是障碍物dp[0]在之前的迭代里已经被置为0这里无需额外操作 // 所以j 0时什么都不做或者写成 dp[j] dp[j]; } else { dp[j] dp[j] dp[j - 1]; } } } return dp[n - 1]; } }这个代码里j 0的分支要重点解释。第一列在滚动更新中比较特殊它没有左边邻居只有上方邻居。在二维dp里第一列的更新是dp[i][0] dp[i-1][0]只要上方不是障碍物第一列的值会一直保持为1一旦上方某个位置是障碍物这一列就断了。在一维数组里dp[0]天然保存的是上一行第0列的值所以只要遇到障碍物时把它清零其余时候保持原样就行。这就是为什么j 0时不操作。但这里有一个必须警惕的细节如果障碍物出现在第0行第0列之外的第一列某个位置比如grid[2][0] 1那么第2行遍历到j0时dp[0]会被清零第3行继续遍历时dp[0]保持0路径信息就正确地被阻断了。这个逻辑我在实现时验证过是对的。可万一你写成j 0时 dp[j] 1那第一列就永远满血复活答案直接错。这个坑非常隐蔽我当初就是在优化时踩了一次排查了好久才发现是这里的问题。Python的空间优化版代码逻辑完全一样只是语法不同这里不再重复贴。但一句话提醒不要用numpy之类的库做这种题LeetCode环境不保证有用纯Python列表就足够。6. 常见问题与排查技巧实录6.1 输出比预期大的排查思路这是我刷这道题时第一次WA的场景印象很深。我看了一眼题目写完二维dp信心满满地提交结果一个测试用例输出比预期大得多。我当时的直觉反应是是不是障碍物没生效于是开始逐行检查。最后发现问题出在初始化我把第一行第一列都直接铺了1完全无视了障碍物。当时那个测试用例是在第一行中间放了一个障碍物导致后续格子被错误地标记为可达。修复方法就是把初始化的铺1改成遇障碍物截断。如果你也遇到输出比预期大的情况大概率就是初始化漏了阻断逻辑。建议你在本地把obstacleGrid打印出来单独验证第一行和第一列的值是否合理。6.2 输出为0但预期不为0的排查思路反过来输出比预期小甚至直接为0通常不是初始化的问题而是转移方程里把不可达的部分过度置0了。比如你在循环里对每个格子都先判断if (obstacleGrid[i][j] 1) dp[i][j] 0; else dp[i][j] dp[i - 1][j] dp[i][j - 1];理论上没问题。但如果你在判断之前错误地给dp数组全部初始化为0然后直接在每次循环里累加可能导致某些本应有路径数传递的格子没做累加。还有一个常见问题一开始的起点判断。如果起点是障碍物直接返回0这个逻辑写漏了而在初始化代码里先执行了dp[0][0] 1那即使起点是障碍物程序也会错误地开始递推。LeetCode的测试用例对这种场景抓得很严所以千万要记得前置判断。6.3 Python二维数组的浅拷贝坑前面提过[[0] * n] * m的问题这里详细说下。这个写法外层乘mPython会创建m个指向同一个列表对象的引用。当你执行dp[1][2] 5时实际上修改的是那个共享列表的第2个元素所有行看起来都被改了。这个问题在简单的二维dp里极易被忽略因为你只在某一处修改dp[i][j]打印的时候会发现那一列所有的值都变了完全摸不着头脑。我用一个表格列出这个坑的对比表现初始化方式dp[1][2] 5 后打印dp说明[[0]*n for _ in range(m)]只有第1行第2列变成5正确每行独立[[0]*n] * m所有行的第2列都变成5错误m行共享同一个列表所以看到这行代码的写法心里要立刻拉起警报凡是用[[0]*n] * m来初始化二维数组基本都可以判定为潜在bug。6.4 一维空间优化版在障碍物出现在第一列时的正确性这个问题是我自己在做空间优化时特意验证过的值得记一笔。假如第一列的某个位置是障碍物比如grid[2][0] 1那么第0行初始化后dp[0] 1。第1行遍历j0时grid[1][0]不是障碍物dp[0]保持1。第2行遍历j0时grid[2][0]是障碍物dp[0]被置为0。第3行遍历j0时grid[3][0]不是障碍物dp[0]保持0因为没有被重新赋值成1。所以从第2行开始第一列的路径数正确地变为了0并且不会因为后面行的遍历而自动恢复。这个行为的正确性完全依赖一个前提j 0时不做任何修复操作。如果你不小心在j 0分支写了dp[j] 1那这个障碍物的阻断效果就失效了。这一点我建议你亲手跑一个3x3的用例去验证体会更深。6.5 常见边界测试用例参考速查表我把这道题考察过的边界情况整理成一个表刷题时可以直接当成checklist用测试场景网格示例预期结果考察点起点即障碍物[[1]]0起点判断终点是障碍物[[0,0],[0,1]]0递推自然覆盖无障碍纯净网格[[0,0],[0,0]]2与62题一致性第一行有障碍物[[0,1,0],[0,0,0]]0第一行初始化截断第一列有障碍物[[0],[1],[0]]0第一列初始化截断单行网格[[0,0,0]]1特殊尺寸单列网格[[0],[0],[0]]1特殊尺寸障碍物形成绕行路径[[0,0,0],[0,1,0],[0,0,0]]2常规递推正确性这张表里的前几行我在面试模拟时被问过很多次尤其起点是障碍物这个用例很多人会在循环里处理但没有前置判断导致起点为1时还在初始化里把dp[0][0]赋成1。真的这个细节值得反复强调。7. 工程化扩展思路从力扣题到现实路径规划的迁移7.1 与寻路问题的关系聊完了题目本身我想再多说几句。很多读者刷这道题的时候会把它当成一个纯粹的算法练习但它在真实世界中是有对应原型的。想象一个仓储机器人在货架之间移动网格表示地面障碍物是货架或临时堆放的包裹机器人的任务就是规划一条从入库口到出库口的路径而且通常希望统计有多少种可行走法用来评估不同调度策略的冗余度。LeetCode 63题正是这个原型的数学抽象简单到只考虑两个运动方向也正因为简单它才是学习动态规划如何从现实问题抽象为状态转移的绝佳素材。从工程角度讲一旦你理解了这道题的dp递推后续很多进阶路线都变得平滑比如把只向右下改成四方向移动那就变成回溯或带记忆化的DFS把计数改成求最短路径步数就变成BFS或Dijkstra把静态障碍物改成动态障碍物障碍物会随时间变化那就要引入时间维度的状态扩展。很多人学算法觉得学了没处用其实是缺少把题目逻辑往现实场景上套的一步。7.2 从二维DP到记忆化搜索的等价转换还有一个值得提的知识点动态规划和记忆化搜索本质上是同一套思路的两种写法。LeetCode 63可以用自底向上的二维dp来写也可以用自顶向下的递归加memo数组来写。前者从左上角开始递推后者从右下角开始递归每次询问到达这个格子的路径数如果遇到障碍物返回0如果已经算过就直接返回缓存值。两种做法的时间复杂度和空间复杂度完全一样区别只是代码风格。我建议有精力的同学把记忆化搜索版本也写一写因为这能帮你建立更通用的递归思维。很多难度更高的题比如带状态压缩的DP递归加缓存的思路往往比递推更容易构建。但这道题的递推版本其实已经足够直观所以我个人的体会是如果你想快速AC递推优先如果你是理论学习派两种都写一遍加深理解。7.3 如果要扩展到更大的网格和更多障碍物有一种情况是网格特别大、障碍物密度特别高比如m、n都到几百障碍物多到把路径几乎堵死。此时二维dp的空间还可能撑得住几百乘几百但如果m、n上千虽然题目数据范围不会变态到那个程度工程里却会遇到。这时候有两条路一条是把dp从二维压到一维前面已经讲了另一条是如果障碍物非常稀疏可以把连续无障碍的行/列压缩使用压缩行技术把二维网格的维度缩减到障碍物数量级别。后者更偏竞赛技巧不在本文展开但你可以把它当成一个进阶方向。8. 实操心得与最终建议这道题刷完之后我自己养成了几个习惯分享给你参考。第一凡是有障碍物的网格DP题写代码之前先把起点是否为障碍物写成一个独立判断。这个习惯后来帮我避了不少雷不只是LeetCode 63很多类似题目比如不同路径系列的变种都有同样的前置条件。第二初始化第一行和第一列时不要图省事用固定值铺底而是顺着上一个格子的值递推。这条纪律看起来简单但能一次就避开最隐蔽的边界bug。第三空间优化版代码写完最好拿一个「障碍物出现在第一行/第一列」的用例手跑一遍确认dp[j]在j0时的行为符合预期。因为一维数组的代码比二维更绕一旦写错调试成本反而更高。第四做这道题的过程中一定要顺手把Python列表初始化的浅拷贝问题彻底搞明白。这个坑在很多二维DP题目里都会出现早踩早长记性。从难度梯度上看LeetCode 63处在动态规划入门到进阶的过渡带。它比62多了障碍物的条件但没有引入贪心选择、区间划分这些更难的概念。把这一题吃透你能掌握的知识可以不夸张地说覆盖了很大一类网格DP题路径计数、最小路径和、最大正方形它们共享同一套按行走、按列扫、状态依赖左和上的框架。我自己在后来刷LeetCode 64最小路径和时几乎是顺手就写出了正确代码因为框架已经烂熟于心。最后说点实在的。刷题不是背代码而是练建模能力。看到一道题先别急着写循环先花一分钟想一想状态是什么转移是什么边界是什么LeetCode 63的这三个问题都非常清晰很适合用来训练这种思考肌肉。如果你能顺着这篇文章的思路自己把二维dp版、一维优化版、记忆化搜索版都独立写一遍并且每版都能说清楚为什么这样初始化那这道题的价值你就算是拿满了。