1.题目背景与描述题目编号LeetCode 63. 不同路径 II (Unique Paths II)难度中等相关标签数组、动态规划、矩阵题目描述一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。示例 1输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]]输出2解释3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径1. 向右 - 向右 - 向下 - 向下2. 向下 - 向下 - 向右 - 向右2.算法思路演进面对网格路径统计问题通常有三种思考方向深度优先搜索DFS、记忆化搜索DFS 备忘录以及动态规划DP。我们依次探讨它们的可行性与优劣。2.1朴素深度优先搜索DFS—— 逻辑正确但会超时最直观的思路是使用 DFS 穷举所有可能的路径。每次向右或向下走遇到障碍物或越界则返回到达终点则计数加一。代码实现class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { return DFS(obstacleGrid, 0, 0); } private: int DFS(vectorvectorint grid, int i, int j) { int m grid.size(); int n grid[0].size(); // 越界或遇到障碍物此路不通 if (i m || j n || grid[i][j] 1) { return 0; } // 到达终点找到一条有效路径 if (i m - 1 j n - 1) { return 1; } // 递归计算向下和向右的路径数之和 int downPaths DFS(grid, i 1, j); int rightPaths DFS(grid, i, j 1); return downPaths rightPaths; } };缺陷分析时间复杂度为指数级O2mn。当网格稍大如 20x20时路径总数会达到数百亿条导致超时Time Limit Exceeded。因此纯 DFS 无法通过本题。2.2记忆化搜索DFS Memoization—— 优化后的 DFS为了消除 DFS 中的重复计算我们可以引入一个 memo 数组。当某个格子 (i, j) 的路径数被计算过一次后将其存入 memo下次再访问时直接返回。代码实现class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(); int n obstacleGrid[0].size(); // 初始化 memo 数组-1 表示未计算 vectorvectorint memo(m, vectorint(n, -1)); return DFS(obstacleGrid, memo, 0, 0); } private: int DFS(vectorvectorint grid, vectorvectorint memo, int i, int j) { int m grid.size(); int n grid[0].size(); if (i m || j n || grid[i][j] 1) return 0; if (i m - 1 j n - 1) return 1; if (memo[i][j] ! -1) return memo[i][j]; int downPaths DFS(grid, memo, i 1, j); int rightPaths DFS(grid, memo, i, j 1); memo[i][j] downPaths rightPaths; return memo[i][j]; } };复杂度时间复杂度O(m×n)空间复杂度O(m×n)递归栈 memo 数组。可以通过但空间上仍有优化空间。2.3动态规划DP—— 本题的最优解核心思想由于机器人只能向下或向右移动到达格子 (i, j) 的路径只能来自上方 (i-1, j) 或左方 (i, j-1)。因此状态转移方程为dp[i][j] dp[i-1][j] dp[i][j-1]障碍物处理如果 (i, j) 是障碍物obstacleGrid[i][j] 1则 dp[i][j] 0。边界条件起点 (0,0)若为障碍物直接返回 0否则 dp[0][0] 1。第一行 dp[0][j]只能从左边走来若左边有障碍物则后续全为 0。第一列 dp[i][0]只能从上边走来若上边有障碍物则后续全为 0。二维 DP 代码class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(); int n obstacleGrid[0].size(); if (obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1) return 0; vectorvectorlong long dp(m, vectorlong long(n, 0)); dp[0][0] 1; // 初始化第一列 for (int i 1; i m; i) { if (obstacleGrid[i][0] 0) dp[i][0] dp[i-1][0]; } // 初始化第一行 for (int j 1; j n; j) { if (obstacleGrid[0][j] 0) 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] 0) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } } return (int)dp[m-1][n-1]; } };2.4空间优化 DP —— 终极方案观察状态转移方程 dp[i][j] dp[i-1][j] dp[i][j-1]可以发现当前行的状态只依赖于上一行的状态和当前行左侧的状态。因此我们可以将二维数组压缩为一维数组 dp[j]。优化原理在遍历第 i 行时更新前的 dp[j] 保存的是 dp[i-1][j]上一行。更新后的 dp[j-1] 保存的是 dp[i][j-1]当前行左侧。因此dp[j] dp[j] dp[j-1] 即可完成状态转移。最终代码class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int m obstacleGrid.size(); int n obstacleGrid[0].size(); vectorlong long dp(n, 0); // 起点初始化 if (obstacleGrid[0][0] 0) { dp[0] 1; } else { return 0; // 起点有障碍物直接返回 } for (int i 0; i m; i) { for (int j 0; j n; j) { // 遇到障碍物置 0 if (obstacleGrid[i][j] 1) { dp[j] 0; continue; } // 起点已初始化跳过 if (i 0 j 0) continue; // 状态转移dp[j] 旧值代表上方dp[j-1] 新值代表左方 if (j 0) { dp[j] dp[j] dp[j-1]; } // j 0 时只能从上方来dp[0] 保持不变 } } return (int)dp[n-1]; } };3.复杂度分析算法时间复杂度空间复杂度是否推荐朴素 DFSO2mnOmn❌ 超时记忆化搜索Om×nOm×n✅ 可行二维 DPOm×nOm×n✅ 推荐一维 DP优化Om×nOn⭐最优