资讯详情

深入了解 · 专业解读

LeetCode 63 Unique Paths II 深度解析：带障碍网格的四种动态规划解法与多语言实现

发布时间：2026/9/19 2:14:48
LeetCode 63 Unique Paths II 深度解析：带障碍网格的四种动态规划解法与多语言实现 LeetCode 63 Unique Paths II 深度解析带障碍网格的四种动态规划解法与多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 63「不同路径 IIUnique Paths II」为核心系统讲解在存在障碍物的m x n网格中统计唯一路径数的四种动态规划解法——自顶向下记忆化递归、自底向上表格填充、一维空间优化与原地In-Place改造并对照本仓库leetcode中 python、cpp、go 等真实源码说明工程化细节。读完本文你将掌握二维网格类 DP 的完整思考链条能独立写出任意语言版本并避开全部经典陷阱。前置知识在动手解决本题之前建议先熟练掌握以下三块基础动态规划Dynamic Programming——理解记忆化自顶向下与表格填充自底向上两种范式以及「重叠子问题」与「最优子结构」的含义二维网格遍历2D Grid Traversal——熟悉按行、按列索引访问矩阵元素递归Recursion——能够通过把大问题拆解为更小的子问题来构造解法。这些前置知识与本仓库中其他网格类题目如 unique-paths 系列 之外的矩阵 DP 题一脉相承是面试与刷题体系中的标准能力项。问题描述与题目语义给定一个m x n的整数数组grid机器人初始位于左上角grid[0][0]目标移动到右下角grid[m-1][n-1]。机器人任意时刻只能向右或向下移动。网格中用1表示障碍物、0表示空地路径不能经过任何障碍物。需要返回机器人到达右下角的唯一路径总数。以仓库中 cpp/0063-unique-paths-ii.cpp 顶部注释给出的经典样例为例obstacleGrid [[0,0,0], [0,1,0], [0,0,0]]3x3 网格正中央有一个障碍物此时恰好有两条路径可以到达右下角右 → 右 → 下 → 下下 → 下 → 右 → 右因此答案返回2。解法一动态规划自顶向下 / 记忆化递归核心直觉我们希望统计从左上角到右下角的所有可行路径但某些格子被障碍物阻断。任意格子处只能向右或向下移动这天然导出一个递归结构某个格子出发的路径数 它下方格子的路径数 它右方格子的路径数。一旦撞到障碍物或越界该方向贡献的路径数为0。由于大量子问题相互重叠同一个格子会被不同路线反复访问我们使用记忆化memoization缓存已计算结果避免冗余计算。算法步骤定义递归函数dfs(r, c)返回从格子(r, c)到终点的路径数基准情形Base Cases若r或c越界或当前格子是障碍物返回0若到达终点(M-1, N-1)返回1若(r, c)的结果已存在于dp缓存中直接返回缓存值否则计算dfs(r1, c) dfs(r, c1)并存入dp调用dfs(0, 0)得到总路径数。多语言实现class Solution: def uniquePathsWithObstacles(self, grid: List[List[int]]) - int: M, N len(grid), len(grid[0]) dp {(M - 1, N - 1): 1} def dfs(r, c): if r M or c N or grid[r][c]: return 0 if (r, c) in dp: return dp[(r, c)] dp[(r, c)] dfs(r 1, c) dfs(r, c 1) return dp[(r, c)] return dfs(0, 0)public class Solution { private int[][] dp; public int uniquePathsWithObstacles(int[][] grid) { int M grid.length, N grid[0].length; dp new int[M][N]; for (int i 0; i M; i) { for (int j 0; j N; j) { dp[i][j] -1; } } return dfs(0, 0, grid, M, N); } private int dfs(int r, int c, int[][] grid, int M, int N) { if (r M || c N || grid[r][c] 1) { return 0; } if (r M - 1 c N - 1) { return 1; } if (dp[r][c] ! -1) { return dp[r][c]; } dp[r][c] dfs(r 1, c, grid, M, N) dfs(r, c 1, grid, M, N); return dp[r][c]; } }class Solution { private: vectorvectorint dp; public: int uniquePathsWithObstacles(vectorvectorint grid) { int M grid.size(), N grid[0].size(); dp.resize(M, vectorint(N, -1)); return dfs(0, 0, grid, M, N); } private: int dfs(int r, int c, vectorvectorint grid, int M, int N) { if (r M || c N || grid[r][c] 1) { return 0; } if (r M - 1 c N - 1) { return 1; } if (dp[r][c] ! -1) { return dp[r][c]; } dp[r][c] dfs(r 1, c, grid, M, N) dfs(r, c 1, grid, M, N); return dp[r][c]; } };class Solution { /** * param {number[][]} grid * return {number} */ uniquePathsWithObstacles(grid) { const M grid.length, N grid[0].length; const dp Array.from({ length: M }, () Array(N).fill(-1)); const dfs (r, c) { if (r M || c N || grid[r][c] 1) { return 0; } if (r M - 1 c N - 1) { return 1; } if (dp[r][c] ! -1) { return dp[r][c]; } dp[r][c] dfs(r 1, c) dfs(r, c 1); return dp[r][c]; }; return dfs(0, 0); } }public class Solution { private int[,] dp; public int UniquePathsWithObstacles(int[][] grid) { int M grid.Length, N grid[0].Length; dp new int[M, N]; for (int i 0; i M; i) { for (int j 0; j N; j) { dp[i, j] -1; } } return Dfs(0, 0, grid, M, N); } private int Dfs(int r, int c, int[][] grid, int M, int N) { if (r M || c N || grid[r][c] 1) { return 0; } if (r M - 1 c N - 1) { return 1; } if (dp[r, c] ! -1) { return dp[r, c]; } dp[r, c] Dfs(r 1, c, grid, M, N) Dfs(r, c 1, grid, M, N); return dp[r, c]; } }func uniquePathsWithObstacles(grid [][]int) int { M, N : len(grid), len(grid[0]) dp : make([][]int, M) for i : range dp { dp[i] make([]int, N) for j : range dp[i] { dp[i][j] -1 } } var dfs func(r, c int) int dfs func(r, c int) int { if r M || c N || grid[r][c] 1 { return 0 } if r M-1 c N-1 { return 1 } if dp[r][c] ! -1 { return dp[r][c] } dp[r][c] dfs(r1, c) dfs(r, c1) return dp[r][c] } return dfs(0, 0) }class Solution { fun uniquePathsWithObstacles(grid: ArrayIntArray): Int { val M grid.size val N grid[0].size val dp Array(M) { IntArray(N) { -1 } } fun dfs(r: Int, c: Int): Int { if (r M || c N || grid[r][c] 1) { return 0 } if (r M - 1 c N - 1) { return 1 } if (dp[r][c] ! -1) { return dp[r][c] } dp[r][c] dfs(r 1, c) dfs(r, c 1) return dp[r][c] } return dfs(0, 0) } }class Solution { func uniquePathsWithObstacles(_ grid: [[Int]]) - Int { let M grid.count, N grid[0].count var dp [[Int]](repeating: Int, count: M) func dfs(_ r: Int, _ c: Int) - Int { if r M || c N || grid[r][c] 1 { return 0 } if r M - 1 c N - 1 { return 1 } if dp[r][c] ! -1 { return dp[r][c] } dp[r][c] dfs(r 1, c) dfs(r, c 1) return dp[r][c] } return dfs(0, 0) } }impl Solution { pub fn unique_paths_with_obstacles(obstacle_grid: VecVeci32) - i32 { let m obstacle_grid.len(); let n obstacle_grid[0].len(); let mut dp vec![vec![-1; n]; m]; fn dfs(r: usize, c: usize, grid: [Veci32], dp: mut VecVeci32, m: usize, n: usize) - i32 { if r m || c n || grid[r][c] 1 { return 0; } if r m - 1 c n - 1 { return 1; } if dp[r][c] ! -1 { return dp[r][c]; } dp[r][c] dfs(r 1, c, grid, dp, m, n) dfs(r, c 1, grid, dp, m, n); dp[r][c] } dfs(0, 0, obstacle_grid, mut dp, m, n) } }时间复杂度与空间复杂度时间复杂度$O(m * n)$空间复杂度$O(m * n)$其中 $m$ 为行数$n$ 为列数。每个格子至多被计算一次并缓存递归调用栈深度最坏为 $O(m n)$可并入空间复杂度考量。解法二动态规划自底向上 / 表格填充核心直觉不再从起点递归而是从终点反向迭代构建解。每个格子存储「从该格子出发到达终点的路径数」该值等于其下方格子的路径数与右方格子的路径数之和。障碍物的计数直接置为0因为没有路径能穿过它。算法步骤若起点或终点本身是障碍物直接返回0创建一个带额外一行一列的二维dp表初始化为0用于优雅处理边界令dp[M-1][N-1] 1表示「从终点到终点」恰好有 1 条路径从右下角向左上角迭代若当前格子是障碍物置dp[r][c] 0否则置dp[r][c] dp[r1][c] dp[r][c1]返回dp[0][0]作为答案。多语言实现class Solution: def uniquePathsWithObstacles(self, grid: List[List[int]]) - int: M, N len(grid), len(grid[0]) if grid[0][0] 1 or grid[M - 1][N - 1] 1: return 0 dp [[0] * (N 1) for _ in range(M 1)] dp[M - 1][N - 1] 1 for r in range(M - 1, -1, -1): for c in range(N - 1, -1, -1): if grid[r][c] 1: dp[r][c] 0 else: dp[r][c] dp[r 1][c] dp[r][c] dp[r][c 1] return dp[0][0]public class Solution { public int uniquePathsWithObstacles(int[][] grid) { int M grid.length, N grid[0].length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } int[][] dp new int[M 1][N 1]; dp[M - 1][N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[r][c] 0; } else { dp[r][c] dp[r 1][c]; dp[r][c] dp[r][c 1]; } } } return dp[0][0]; } }class Solution { public: int uniquePathsWithObstacles(vectorvectorint grid) { int M grid.size(), N grid[0].size(); if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } vectorvectoruint dp(M 1, vectoruint(N 1, 0)); dp[M - 1][N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[r][c] 0; } else { dp[r][c] dp[r 1][c]; dp[r][c] dp[r][c 1]; } } } return dp[0][0]; } };class Solution { /** * param {number[][]} grid * return {number} */ uniquePathsWithObstacles(grid) { const M grid.length, N grid[0].length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } const dp Array.from({ length: M 1 }, () Array(N 1).fill(0)); dp[M - 1][N - 1] 1; for (let r M - 1; r 0; r--) { for (let c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[r][c] 0; } else { dp[r][c] dp[r 1][c]; dp[r][c] dp[r][c 1]; } } } return dp[0][0]; } }public class Solution { public int UniquePathsWithObstacles(int[][] grid) { int M grid.Length, N grid[0].Length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } int[,] dp new int[M 1, N 1]; dp[M - 1, N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[r, c] 0; } else { dp[r, c] dp[r 1, c]; dp[r, c] dp[r, c 1]; } } } return dp[0, 0]; } }func uniquePathsWithObstacles(grid [][]int) int { M, N : len(grid), len(grid[0]) if grid[0][0] 1 || grid[M-1][N-1] 1 { return 0 } dp : make([][]int, M1) for i : range dp { dp[i] make([]int, N1) } dp[M-1][N-1] 1 for r : M - 1; r 0; r-- { for c : N - 1; c 0; c-- { if grid[r][c] 1 { dp[r][c] 0 } else { dp[r][c] dp[r1][c] dp[r][c] dp[r][c1] } } } return dp[0][0] }class Solution { fun uniquePathsWithObstacles(grid: ArrayIntArray): Int { val M grid.size val N grid[0].size if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0 } val dp Array(M 1) { IntArray(N 1) } dp[M - 1][N - 1] 1 for (r in M - 1 downTo 0) { for (c in N - 1 downTo 0) { if (grid[r][c] 1) { dp[r][c] 0 } else { dp[r][c] dp[r 1][c] dp[r][c] dp[r][c 1] } } } return dp[0][0] } }class Solution { func uniquePathsWithObstacles(_ grid: [[Int]]) - Int { let M grid.count, N grid[0].count if grid[0][0] 1 || grid[M - 1][N - 1] 1 { return 0 } var dp [[Int]](repeating: Int, count: M 1) dp[M - 1][N - 1] 1 for r in stride(from: M - 1, through: 0, by: -1) { for c in stride(from: N - 1, through: 0, by: -1) { if grid[r][c] 1 { dp[r][c] 0 } else { dp[r][c] dp[r 1][c] dp[r][c] dp[r][c 1] } } } return dp[0][0] } }impl Solution { pub fn unique_paths_with_obstacles(obstacle_grid: VecVeci32) - i32 { let m obstacle_grid.len(); let n obstacle_grid[0].len(); if obstacle_grid[0][0] 1 || obstacle_grid[m - 1][n - 1] 1 { return 0; } let mut dp vec![vec![0; n 1]; m 1]; dp[m - 1][n - 1] 1; for r in (0..m).rev() { for c in (0..n).rev() { if obstacle_grid[r][c] 1 { dp[r][c] 0; } else { dp[r][c] dp[r 1][c]; dp[r][c] dp[r][c 1]; } } } dp[0][0] } }时间复杂度与空间复杂度时间复杂度$O(m * n)$空间复杂度$O(m * n)$其中 $m$ 为行数$n$ 为列数。这里引入的(M1) x (N1)哨兵行/列能让边界格子统一走dp[r1][c] dp[r][c1]的递推式而无需额外分支判断。解法三动态规划空间优化 / 一维滚动数组核心直觉观察自底向上的递推式每个格子只依赖正下方和正右方两个邻居。由于我们是自下而上逐行处理的因此只需要保留一行即可完成全部计算。更新前的dp[c]代表「下一行同列」的路径数更新后的dp[c1]代表「同行右侧」的路径数。这样空间从 $O(m * n)$ 降到 $O(n)$。算法步骤创建长度为N1的一维数组dp初始化为0令dp[N-1] 1表示终点自下而上遍历每一行对每一列c从右向左处理若该格是障碍物置dp[c] 0否则将dp[c1]累加到dp[c]同时累加来自下方与右方的路径返回dp[0]作为最终答案。多语言实现class Solution: def uniquePathsWithObstacles(self, grid: List[List[int]]) - int: M, N len(grid), len(grid[0]) dp [0] * (N 1) dp[N - 1] 1 for r in range(M - 1, -1, -1): for c in range(N - 1, -1, -1): if grid[r][c]: dp[c] 0 else: dp[c] dp[c 1] return dp[0]public class Solution { public int uniquePathsWithObstacles(int[][] grid) { int M grid.length, N grid[0].length; int[] dp new int[N 1]; dp[N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[c] 0; } else { dp[c] dp[c 1]; } } } return dp[0]; } }class Solution { public: int uniquePathsWithObstacles(vectorvectorint grid) { int M grid.size(), N grid[0].size(); vectoruint dp(N 1, 0); dp[N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[c] 0; } else { dp[c] dp[c 1]; } } } return dp[0]; } };class Solution { /** * param {number[][]} grid * return {number} */ uniquePathsWithObstacles(grid) { const M grid.length, N grid[0].length; const dp new Array(N 1).fill(0); dp[N - 1] 1; for (let r M - 1; r 0; r--) { for (let c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[c] 0; } else { dp[c] dp[c 1]; } } } return dp[0]; } }public class Solution { public int UniquePathsWithObstacles(int[][] grid) { int M grid.Length, N grid[0].Length; int[] dp new int[N 1]; dp[N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (grid[r][c] 1) { dp[c] 0; } else { dp[c] dp[c 1]; } } } return dp[0]; } }func uniquePathsWithObstacles(grid [][]int) int { M, N : len(grid), len(grid[0]) dp : make([]int, N1) dp[N-1] 1 for r : M - 1; r 0; r-- { for c : N - 1; c 0; c-- { if grid[r][c] 1 { dp[c] 0 } else { dp[c] dp[c1] } } } return dp[0] }class Solution { fun uniquePathsWithObstacles(grid: ArrayIntArray): Int { val M grid.size val N grid[0].size val dp IntArray(N 1) dp[N - 1] 1 for (r in M - 1 downTo 0) { for (c in N - 1 downTo 0) { if (grid[r][c] 1) { dp[c] 0 } else { dp[c] dp[c 1] } } } return dp[0] } }class Solution { func uniquePathsWithObstacles(_ grid: [[Int]]) - Int { let M grid.count, N grid[0].count var dp Int dp[N - 1] 1 for r in stride(from: M - 1, through: 0, by: -1) { for c in stride(from: N - 1, through: 0, by: -1) { if grid[r][c] 1 { dp[c] 0 } else { dp[c] dp[c 1] } } } return dp[0] } }impl Solution { pub fn unique_paths_with_obstacles(obstacle_grid: VecVeci32) - i32 { let m obstacle_grid.len(); let n obstacle_grid[0].len(); let mut dp vec![0; n 1]; dp[n - 1] 1; for r in (0..m).rev() { for c in (0..n).rev() { if obstacle_grid[r][c] 1 { dp[c] 0; } else { dp[c] dp[c 1]; } } } dp[0] } }仓库源码佐证本仓库的 python/0063-unique-paths-ii.py 正是以该「空间优化」版本作为主解并明确标注了复杂度注释# Time: O(N*M), Space: O(N) for r in reversed(range(M)): for c in reversed(range(N)): if grid[r][c]: dp[c] 0 elif c 1 N: dp[c] dp[c] dp[c 1] return dp[0]cpp/0063-unique-paths-ii.cpp 的实现则使用vectorlong long dp(n)在入口处先对grid[m-1][n-1]与grid[0][0]做障碍物检查且通过else if (j n-1) continue;跳过最右列终点列的累加——这是对同一思路的另一种边界处理写法。从这些实现可以看出一维滚动数组 逆序遍历是本题在工程上最常用的「最优解」形态。时间复杂度与空间复杂度时间复杂度$O(m * n)$空间复杂度$O(n)$其中 $m$ 为行数$n$ 为列数。解法四动态规划原地 In-Place核心直觉连额外的一维数组都可以省掉直接复用输入网格存储路径计数。关键洞察是——一旦某个格子被处理完就不再需要它的原始值原始值只可能是0或1。我们把grid就地改造成「从该格子到终点的路径数」障碍物统一转化为0因为没有任何路径穿过它。算法步骤若起点或终点有障碍物返回0令grid[M-1][N-1] 1标记终点从右下角向左上角迭代跳过终点格子本身若当前格是障碍物置为0否则计算down right其中down是下方格子的值right是右方格子的值返回grid[0][0]作为答案。多语言实现class Solution: def uniquePathsWithObstacles(self, grid: List[List[int]]) - int: M, N len(grid), len(grid[0]) if grid[0][0] 1 or grid[M - 1][N - 1] 1: return 0 grid[M - 1][N - 1] 1 for r in range(M - 1, -1, -1): for c in range(N - 1, -1, -1): if r M - 1 and c N - 1: continue if grid[r][c] 1: grid[r][c] 0 else: down grid[r 1][c] if r 1 M else 0 right grid[r][c 1] if c 1 N else 0 grid[r][c] down right return grid[0][0]public class Solution { public int uniquePathsWithObstacles(int[][] grid) { int M grid.length, N grid[0].length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } grid[M - 1][N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (r M - 1 c N - 1) { continue; } if (grid[r][c] 1) { grid[r][c] 0; } else { int down (r 1 M) ? grid[r 1][c] : 0; int right (c 1 N) ? grid[r][c 1] : 0; grid[r][c] down right; } } } return grid[0][0]; } }class Solution { public: int uniquePathsWithObstacles(vectorvectorint grid) { int M grid.size(), N grid[0].size(); if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } grid[M - 1][N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (r M - 1 c N - 1) { continue; } if (grid[r][c] 1) { grid[r][c] 0; } else { uint down (r 1 M) ? grid[r 1][c] : 0; uint right (c 1 N) ? grid[r][c 1] : 0; grid[r][c] down right; } } } return grid[0][0]; } };class Solution { /** * param {number[][]} grid * return {number} */ uniquePathsWithObstacles(grid) { const M grid.length, N grid[0].length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } grid[M - 1][N - 1] 1; for (let r M - 1; r 0; r--) { for (let c N - 1; c 0; c--) { if (r M - 1 c N - 1) { continue; } if (grid[r][c] 1) { grid[r][c] 0; } else { const down r 1 M ? grid[r 1][c] : 0; const right c 1 N ? grid[r][c 1] : 0; grid[r][c] down right; } } } return grid[0][0]; } }public class Solution { public int UniquePathsWithObstacles(int[][] grid) { int M grid.Length, N grid[0].Length; if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0; } grid[M - 1][N - 1] 1; for (int r M - 1; r 0; r--) { for (int c N - 1; c 0; c--) { if (r M - 1 c N - 1) { continue; } if (grid[r][c] 1) { grid[r][c] 0; } else { int down (r 1 M) ? grid[r 1][c] : 0; int right (c 1 N) ? grid[r][c 1] : 0; grid[r][c] down right; } } } return grid[0][0]; } }func uniquePathsWithObstacles(grid [][]int) int { M, N : len(grid), len(grid[0]) if grid[0][0] 1 || grid[M-1][N-1] 1 { return 0 } grid[M-1][N-1] 1 for r : M - 1; r 0; r-- { for c : N - 1; c 0; c-- { if r M-1 c N-1 { continue } if grid[r][c] 1 { grid[r][c] 0 } else { down : 0 if r1 M { down grid[r1][c] } right : 0 if c1 N { right grid[r][c1] } grid[r][c] down right } } } return grid[0][0] }class Solution { fun uniquePathsWithObstacles(grid: ArrayIntArray): Int { val M grid.size val N grid[0].size if (grid[0][0] 1 || grid[M - 1][N - 1] 1) { return 0 } grid[M - 1][N - 1] 1 for (r in M - 1 downTo 0) { for (c in N - 1 downTo 0) { if (r M - 1 c N - 1) { continue } if (grid[r][c] 1) { grid[r][c] 0 } else { val down if (r 1 M) grid[r 1][c] else 0 val right if (c 1 N) grid[r][c 1] else 0 grid[r][c] down right } } } return grid[0][0] } }class Solution { func uniquePathsWithObstacles(_ grid: [[Int]]) - Int { var grid grid let M grid.count, N grid[0].count if grid[0][0] 1 || grid[M - 1][N - 1] 1 { return 0 } grid[M - 1][N - 1] 1 for r in stride(from: M - 1, through: 0, by: -1) { for c in stride(from: N - 1, through: 0, by: -1) { if r M - 1 c N - 1 { continue } if grid[r][c] 1 { grid[r][c] 0 } else { let down (r 1 M) ? grid[r 1][c] : 0 let right (c 1 N) ? grid[r][c 1] : 0 grid[r][c] down right } } } return grid[0][0] } }impl Solution { pub fn unique_paths_with_obstacles(mut obstacle_grid: VecVeci32) - i32 { let m obstacle_grid.len(); let n obstacle_grid[0].len(); if obstacle_grid[0][0] 1 || obstacle_grid[m - 1][n - 1] 1 { return 0; } obstacle_grid[m - 1][n - 1] 1; for r in (0..m).rev() { for c in (0..n).rev() { if r m - 1 c n - 1 { continue; } if obstacle_grid[r][c] 1 { obstacle_grid[r][c] 0; } else { let down if r 1 m { obstacle_grid[r 1][c] } else { 0 }; let right if c 1 n { obstacle_grid[r][c 1] } else { 0 }; obstacle_grid[r][c] down right; } } } obstacle_grid[0][0] } }注意原地方案会破坏输入数组。Swift 与 Rust 版本通过var grid grid/mut obstacle_grid显式声明可变拷贝说明在真实工程中若上游仍需使用原始网格应先做拷贝或改用解法三。时间复杂度与空间复杂度时间复杂度$O(m * n)$空间复杂度$O(1)$ 额外空间复用输入网格其中 $m$ 为行数$n$ 为列数。常见陷阱Common Pitfalls陷阱一未检查起点或终点是否有障碍物如果起点grid[0][0]或终点grid[M-1][N-1]是障碍物那么路径数必然为0。遗漏这个检查会导致错误结果——例如解法二与解法四都要求先做这一前置判断。陷阱二基准行/列初始化错误填充第一行或第一列时障碍物之后的所有格子路径数都应为0。一个常见错误是把整条边都初始化为1完全没有考虑障碍物会阻断其后的所有格子# 错误没有考虑障碍物阻断路径 for c in range(N): dp[0][c] 1 # 正确遇到障碍物立即停止 for c in range(N): if grid[0][c] 1: break dp[0][c] 1陷阱三混淆障碍物数值与路径计数在 In-Place 方案中输入里障碍物标记为1但 DP 数组中它必须变成0。若混淆这两个语义障碍物会被错误地当作「有 1 条路径」从而多算。陷阱四网格迭代的越界Off-by-One错误自底向上或从右向左迭代时务必确认循环边界正确。从M-1递减到0Python 中应写作range(M-1, -1, -1)而不是range(M-1, 0, -1)——后者会漏掉第一行索引 0。四种解法对比与工程选型解法思路时间复杂度空间复杂度特点解法一 自顶向下记忆化递归 缓存$O(m*n)$$O(m*n)$直观、易写适合先验证思路解法二 自底向上表格哨兵行列 逆序填表$O(m*n)$$O(m*n)$无递归栈风险边界处理优雅解法三 空间优化一维滚动数组复用一行$O(m*n)$$O(n)$面试推荐写法本仓库 python 主解解法四 原地In-Place复用输入网格$O(m*n)$$O(1)$ 额外最省内存但会破坏输入数据若以n远小于m的宽网格为输入解法三的空间收益更为显著解法四则适合对内存极度敏感且不介意修改输入的场景。需要说明的是上述复杂度均为基于网格尺寸 $m \times n$ 的理论结论实际以评测环境为准。延伸阅读本题姊妹题无障碍版本为 Unique Paths递推关系完全一致只是少了对障碍物的判断分支相关网格 DP 题目可参考本仓库 README.md 中按专题整理的题解索引本题的完整题解文档位于 articles/unique-paths-ii.md多语言源码分别位于 python/0063-unique-paths-ii.py、java/0063-unique-paths-ii.java、cpp/0063-unique-paths-ii.cpp、javascript、go/0063-unique-paths-ii.go、kotlin/0063-unique-paths-ii.kt、swift/0063-unique-paths-ii.swift、rust/0063-unique-paths-ii.rs 等目录下可作为多语言对照学习的参考实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

相关新闻