LeetCode 63 不同路径 II 题解带障碍物的网格动态规划与空间压缩实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解围绕 LeetCode 63「不同路径 II」Unique Paths II展开讲解如何在 m x n 网格存在障碍物的情况下统计从左上角到右下角的所有可行路径数。文章以 problems/63.unique-paths-ii.md 的官方题解为主体骨架完整覆盖题目约束、动态规划状态定义与转移方程、记忆化递归、二维 DP 与一维滚动数组三种实现并结合仓库中的 动态规划专题 与姊妹题 62. 不同路径 进行纵深补充读完后你将掌握「二维爬楼梯」类计数 DP 的标准解法套路以及面试高频考点——如何把空间复杂度从 O(M*N) 压缩到 O(N)。题目回顾在网格中加入障碍物一个机器人位于一个 m x n 网格的左上角起始点标记为 Start。机器人每次只能向下或者向右移动一步目标是到达网格的右下角标记为 Finish。与无任何限制的 62. 不同路径 不同本题中网格内存在障碍物需要统计的是从左上角到右下角一共有多少条不同的路径。网格中的障碍物和空位置分别用1和0来表示。说明m和n的值均不超过100。示例 1输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2解释3x3 网格的正中间有一个障碍物从左上角到右下角一共有 2 条不同的路径向右 - 向右 - 向下 - 向下向下 - 向下 - 向右 - 向右前置知识为什么这是一道典型的动态规划题本题的前置知识是动态规划。仓库的 动态规划到底有多难 专题中给出了理解 DP 的两个关键性质最优子结构如果问题的最优解所包含的子问题的解也是最优的则该问题具有最优子结构性质。无后效性子问题的解一旦确定就不再改变不受之后更大问题的求解决策影响。对于本题由于机器人只能向下和向右移动到达格子(i, j)的方式只有两种从上方(i-1, j)走下来或从左边(i, j-1)走过来。因此「到达(i, j)的路径总数」只依赖「到达它上方和左方格子的路径总数」子问题之间互不影响完全满足无后效性。这也正是 thinkings/dynamic-programming.md 中反复强调的「二维爬楼梯」模型62 题与爬楼梯的区别仅在于从一维变成了二维而 63 题则是在 62 题的基础上加入了「障碍物清零」这一额外限制。在 collections/medium.md 的中等难度题单中62 题也被收录其中是面试中动态规划入门的常客。核心思路状态定义与状态转移方程状态定义是动态规划的核心。本题的状态定义如下dp[i][j]表示到达格子obstacleGrid[i - 1][j - 1]的所有路径数。由于机器人只能右移和下移dp[i][j]的递推关系非常直观第[i, j]个格子的路径总数等于[i - 1, j]与[i, j - 1]的路径总数之和因为第[i, j]个格子一定是从左边或者上面移动过来的。而障碍物的存在给转移加上了限制具体来说就是如果当前格子是障碍物则dp[i][j] 0否则dp[i][j] dp[i - 1][j] dp[i][j - 1]。该转移方程可以用仓库 assets/problems/62.unique-paths-3.png 中 62 题的状态转移循环示意图来直观理解——外层循环逐行、内层循环逐列地枚举状态红色数字表示「走到第 i 列的总可能数」63 题只是在同样的递推骨架上增加了障碍物判断分支解法一记忆化递归新手推荐入手如果你刚接触动态规划建议先写记忆化递归再将其转化为标准动态规划。记忆化递归的本质是「查表的递归」用哈希表缓存已计算过的状态避免重复子问题的重复计算详见 thinkings/dynamic-programming.md 的「记忆化递归」章节。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) if m 0: return 0 n len(obstacleGrid[0]) lru_cache(None) def dfs(i, j): if i 0 or i m or j 0 or j n: return 0 if obstacleGrid[i][j] 1: return 0 if i 0 and j 0: return 1 return dfs(i - 1, j) dfs(i, j - 1) return dfs(m - 1, n - 1)lru_cache(None)可以看成一个哈希表key 是函数参数value 是函数的返回值因此纯函数都可使用lru_cache(None)通过空间换时间来优化性能。递归终止条件有三个越界返回 0、遇到障碍物返回 0、到达起点(0, 0)返回 1。由于递归深度的原因记忆化递归的性能比标准 DP 差不少而直接暴力递归则会超时因此面试中更推荐下面的迭代 DP 写法。解法二标准二维 DP二维 DP 是最直观、最不容易出错的写法。一个实现细节值得注意将dp数组声明为(m 1) x (n 1)大小利用第 0 行、第 0 列作为哨兵全 0从而省去对i - 1、j - 1越界的特殊判断并直接把起点状态放在dp[1][1] 1。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) if obstacleGrid[0][0]: return 0 dp [[0] * (n 1) for _ in range(m 1)] dp[1][1] 1 for i in range(1, m 1): for j in range(1, n 1): if i 1 and j 1: continue if obstacleGrid[i - 1][j - 1] 0: dp[i][j] dp[i - 1][j] dp[i][j - 1] else: dp[i][j] 0 return dp[m][n]两个容易遗漏的边界点起点是障碍物obstacleGrid[0][0]为 1 时直接返回 0此时没有任何路径终点是障碍物由于终点格子的dp值会被障碍物分支置 0最终dp[m][n]自然为 0无需特判。复杂度分析时间复杂度$O(M * N)$空间复杂度$O(M * N)$解法三滚动数组压缩到 O(N)高频考点由于dp[i][j]只依赖于左边的元素和上面的元素空间复杂度可以进一步优化到 O(n)——这正是 problems/63.unique-paths-ii.md 关键点中明确标注的考点。滚动数组的思想在 thinkings/dynamic-programming.md 的「滚动数组优化」小节中有系统讲解当前状态只和前一行或前两个状态有关因此只需要保留一维数组即可。Python3 实现从左到右遍历class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) if obstacleGrid[0][0]: return 0 dp [0] * (n 1) dp[1] 1 for i in range(1, m 1): for j in range(1, n 1): if obstacleGrid[i - 1][j - 1] 0: dp[j] dp[j - 1] else: dp[j] 0 return dp[-1]这里dp[j]更新前保存的是上一行i - 1行第 j 列的值dp[j - 1]是当前行已更新的左侧值两者相加恰好等价于二维写法中的dp[i-1][j] dp[i][j-1]遇到障碍物时把dp[j]清零实现「障碍物格子路径数为 0」的语义。CPP 实现从右到左遍历class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int M obstacleGrid.size(), N obstacleGrid[0].size(); vectorint memo(N, 0); memo[N - 1] 1; for (int i M - 1; i 0; --i) { for (int j N - 1; j 0; --j) { if (obstacleGrid[i][j] 1) memo[j] 0; else memo[j] j N - 1 ? 0 : memo[j 1]; } } return memo[0]; } };注意 C 版本采用从右下角向左上角逆向递推的视角memo[j]表示从(i, j)出发到达终点的路径数起点状态memo[N - 1] 1对应右下角终点。这印证了 thinkings/dynamic-programming.md 中「枚举状态的方向取决于状态转移方程与滚动数组的压缩对应关系」这一结论——正向、逆向遍历都可行但压缩前后dp的语义必须一一对应。复杂度分析时间复杂度$O(M * N)$空间复杂度$O(N)$三种解法对比解法时间复杂度空间复杂度适用场景记忆化递归DFS lru_cache$O(M * N)$$O(M * N)$含调用栈开销入门理解、递归思路练习标准二维 DP$O(M * N)$$O(M * N)$最直观、不易出错面试首选滚动数组一维 DP$O(M * N)$$O(N)$空间受限场景面试加分考点关键点总结记忆化递归用lru_cache(None)缓存纯函数的计算结果以空间换时间消除重叠子问题基本动态规划问题识别「二维爬楼梯」模型状态定义 转移方程 枚举状态三步走空间复杂度可以进一步优化到 O(n)利用「当前状态只依赖左边和上边」的局部性用一维滚动数组覆盖这是本题最常被追问的考点边界处理起点为障碍物直接返回 0终点为障碍物时由于清零语义自然得到 0哨兵行列第 0 行 / 第 0 列可简化越界判断。相关题目62. 不同路径本题的无障碍物版本可先掌握基础递推再对比理解障碍物分支的差异两者互为换皮题动态规划专题系统讲解记忆化递归、最优子结构、无后效性、状态定义、滚动数组优化等核心概念是理解本题递推与压缩技巧的底层读物。从 problems/63.unique-paths-ii.md 可以看出这道题在仓库中被收录为阿里、腾讯、百度、字节等公司的面试常考题。建议读者按「记忆化递归 → 二维 DP → 一维滚动数组」的顺序亲手各写一遍并对照 62 题 体会「无障碍 / 有障碍」两种递推在实现上的细微差别即可彻底掌握这类网格计数 DP。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 63 不同路径 II 题解：带障碍物的网格动态规划与空间压缩实战
LeetCode 63 不同路径 II 题解带障碍物的网格动态规划与空间压缩实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解围绕 LeetCode 63「不同路径 II」Unique Paths II展开讲解如何在 m x n 网格存在障碍物的情况下统计从左上角到右下角的所有可行路径数。文章以 problems/63.unique-paths-ii.md 的官方题解为主体骨架完整覆盖题目约束、动态规划状态定义与转移方程、记忆化递归、二维 DP 与一维滚动数组三种实现并结合仓库中的 动态规划专题 与姊妹题 62. 不同路径 进行纵深补充读完后你将掌握「二维爬楼梯」类计数 DP 的标准解法套路以及面试高频考点——如何把空间复杂度从 O(M*N) 压缩到 O(N)。题目回顾在网格中加入障碍物一个机器人位于一个 m x n 网格的左上角起始点标记为 Start。机器人每次只能向下或者向右移动一步目标是到达网格的右下角标记为 Finish。与无任何限制的 62. 不同路径 不同本题中网格内存在障碍物需要统计的是从左上角到右下角一共有多少条不同的路径。网格中的障碍物和空位置分别用1和0来表示。说明m和n的值均不超过100。示例 1输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2解释3x3 网格的正中间有一个障碍物从左上角到右下角一共有 2 条不同的路径向右 - 向右 - 向下 - 向下向下 - 向下 - 向右 - 向右前置知识为什么这是一道典型的动态规划题本题的前置知识是动态规划。仓库的 动态规划到底有多难 专题中给出了理解 DP 的两个关键性质最优子结构如果问题的最优解所包含的子问题的解也是最优的则该问题具有最优子结构性质。无后效性子问题的解一旦确定就不再改变不受之后更大问题的求解决策影响。对于本题由于机器人只能向下和向右移动到达格子(i, j)的方式只有两种从上方(i-1, j)走下来或从左边(i, j-1)走过来。因此「到达(i, j)的路径总数」只依赖「到达它上方和左方格子的路径总数」子问题之间互不影响完全满足无后效性。这也正是 thinkings/dynamic-programming.md 中反复强调的「二维爬楼梯」模型62 题与爬楼梯的区别仅在于从一维变成了二维而 63 题则是在 62 题的基础上加入了「障碍物清零」这一额外限制。在 collections/medium.md 的中等难度题单中62 题也被收录其中是面试中动态规划入门的常客。核心思路状态定义与状态转移方程状态定义是动态规划的核心。本题的状态定义如下dp[i][j]表示到达格子obstacleGrid[i - 1][j - 1]的所有路径数。由于机器人只能右移和下移dp[i][j]的递推关系非常直观第[i, j]个格子的路径总数等于[i - 1, j]与[i, j - 1]的路径总数之和因为第[i, j]个格子一定是从左边或者上面移动过来的。而障碍物的存在给转移加上了限制具体来说就是如果当前格子是障碍物则dp[i][j] 0否则dp[i][j] dp[i - 1][j] dp[i][j - 1]。该转移方程可以用仓库 assets/problems/62.unique-paths-3.png 中 62 题的状态转移循环示意图来直观理解——外层循环逐行、内层循环逐列地枚举状态红色数字表示「走到第 i 列的总可能数」63 题只是在同样的递推骨架上增加了障碍物判断分支解法一记忆化递归新手推荐入手如果你刚接触动态规划建议先写记忆化递归再将其转化为标准动态规划。记忆化递归的本质是「查表的递归」用哈希表缓存已计算过的状态避免重复子问题的重复计算详见 thinkings/dynamic-programming.md 的「记忆化递归」章节。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) if m 0: return 0 n len(obstacleGrid[0]) lru_cache(None) def dfs(i, j): if i 0 or i m or j 0 or j n: return 0 if obstacleGrid[i][j] 1: return 0 if i 0 and j 0: return 1 return dfs(i - 1, j) dfs(i, j - 1) return dfs(m - 1, n - 1)lru_cache(None)可以看成一个哈希表key 是函数参数value 是函数的返回值因此纯函数都可使用lru_cache(None)通过空间换时间来优化性能。递归终止条件有三个越界返回 0、遇到障碍物返回 0、到达起点(0, 0)返回 1。由于递归深度的原因记忆化递归的性能比标准 DP 差不少而直接暴力递归则会超时因此面试中更推荐下面的迭代 DP 写法。解法二标准二维 DP二维 DP 是最直观、最不容易出错的写法。一个实现细节值得注意将dp数组声明为(m 1) x (n 1)大小利用第 0 行、第 0 列作为哨兵全 0从而省去对i - 1、j - 1越界的特殊判断并直接把起点状态放在dp[1][1] 1。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) if obstacleGrid[0][0]: return 0 dp [[0] * (n 1) for _ in range(m 1)] dp[1][1] 1 for i in range(1, m 1): for j in range(1, n 1): if i 1 and j 1: continue if obstacleGrid[i - 1][j - 1] 0: dp[i][j] dp[i - 1][j] dp[i][j - 1] else: dp[i][j] 0 return dp[m][n]两个容易遗漏的边界点起点是障碍物obstacleGrid[0][0]为 1 时直接返回 0此时没有任何路径终点是障碍物由于终点格子的dp值会被障碍物分支置 0最终dp[m][n]自然为 0无需特判。复杂度分析时间复杂度$O(M * N)$空间复杂度$O(M * N)$解法三滚动数组压缩到 O(N)高频考点由于dp[i][j]只依赖于左边的元素和上面的元素空间复杂度可以进一步优化到 O(n)——这正是 problems/63.unique-paths-ii.md 关键点中明确标注的考点。滚动数组的思想在 thinkings/dynamic-programming.md 的「滚动数组优化」小节中有系统讲解当前状态只和前一行或前两个状态有关因此只需要保留一维数组即可。Python3 实现从左到右遍历class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int: m len(obstacleGrid) n len(obstacleGrid[0]) if obstacleGrid[0][0]: return 0 dp [0] * (n 1) dp[1] 1 for i in range(1, m 1): for j in range(1, n 1): if obstacleGrid[i - 1][j - 1] 0: dp[j] dp[j - 1] else: dp[j] 0 return dp[-1]这里dp[j]更新前保存的是上一行i - 1行第 j 列的值dp[j - 1]是当前行已更新的左侧值两者相加恰好等价于二维写法中的dp[i-1][j] dp[i][j-1]遇到障碍物时把dp[j]清零实现「障碍物格子路径数为 0」的语义。CPP 实现从右到左遍历class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int M obstacleGrid.size(), N obstacleGrid[0].size(); vectorint memo(N, 0); memo[N - 1] 1; for (int i M - 1; i 0; --i) { for (int j N - 1; j 0; --j) { if (obstacleGrid[i][j] 1) memo[j] 0; else memo[j] j N - 1 ? 0 : memo[j 1]; } } return memo[0]; } };注意 C 版本采用从右下角向左上角逆向递推的视角memo[j]表示从(i, j)出发到达终点的路径数起点状态memo[N - 1] 1对应右下角终点。这印证了 thinkings/dynamic-programming.md 中「枚举状态的方向取决于状态转移方程与滚动数组的压缩对应关系」这一结论——正向、逆向遍历都可行但压缩前后dp的语义必须一一对应。复杂度分析时间复杂度$O(M * N)$空间复杂度$O(N)$三种解法对比解法时间复杂度空间复杂度适用场景记忆化递归DFS lru_cache$O(M * N)$$O(M * N)$含调用栈开销入门理解、递归思路练习标准二维 DP$O(M * N)$$O(M * N)$最直观、不易出错面试首选滚动数组一维 DP$O(M * N)$$O(N)$空间受限场景面试加分考点关键点总结记忆化递归用lru_cache(None)缓存纯函数的计算结果以空间换时间消除重叠子问题基本动态规划问题识别「二维爬楼梯」模型状态定义 转移方程 枚举状态三步走空间复杂度可以进一步优化到 O(n)利用「当前状态只依赖左边和上边」的局部性用一维滚动数组覆盖这是本题最常被追问的考点边界处理起点为障碍物直接返回 0终点为障碍物时由于清零语义自然得到 0哨兵行列第 0 行 / 第 0 列可简化越界判断。相关题目62. 不同路径本题的无障碍物版本可先掌握基础递推再对比理解障碍物分支的差异两者互为换皮题动态规划专题系统讲解记忆化递归、最优子结构、无后效性、状态定义、滚动数组优化等核心概念是理解本题递推与压缩技巧的底层读物。从 problems/63.unique-paths-ii.md 可以看出这道题在仓库中被收录为阿里、腾讯、百度、字节等公司的面试常考题。建议读者按「记忆化递归 → 二维 DP → 一维滚动数组」的顺序亲手各写一遍并对照 62 题 体会「无障碍 / 有障碍」两种递推在实现上的细微差别即可彻底掌握这类网格计数 DP。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考