LeetCode-Go 动态规划实战用 Go 实现带障碍物的路径计数Unique Paths II第 63 题【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中第 63 题的题解文档与配套源码完整讲解带障碍物的不同路径数这道经典动态规划题从题目约束、状态转移方程到仓库中uniquePathsWithObstacles函数的逐段实现解读与测试验证方式。读完后你能掌握二维 DP 中障碍格的处理技巧、首行首列边界的初始化方法以及如何在仓库中运行该题的单元测试。题目描述一个机器人位于一个m x n网格的左上角起始点标记为 Start。机器人每次只能向下或者向右移动一步目标是到达网格的右下角标记为 Finish。与第 62 题无障碍版不同的是本题的网格中会出现障碍物障碍物和空地分别用1和0表示需要计算从左上角到右下角共有多少条不同路径约束条件m和n最大为 100。示例源自题解文档 0063.Unique-Paths-II.mdInput: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right - Right - Down - Down 2. Down - Down - Right - Right网格中心是一个障碍物因此绕过它的合法路径恰好有两条先向右再向下或先向下再向右。解题思路第 62 题的加强版仓库题解文档给出的思路可以归纳为三点本题是第 62 题 Unique Paths 的加强版核心仍是简单的 DP动态规划。在无网格障碍的版本中到达任意点的方案数满足dp[i][j] dp[i-1][j] dp[i][j-1]首行首列恒为 1参见 62. Unique Paths.go 的实现。障碍物处理相比第 62 题新增的条件是地图中会出现障碍物处理方法是让障碍格满足dp[i][j] 0——即凡是obstacleGrid[i][j] 1的格子其路径数直接置 0不会向后续格子传播任何方案数。特殊边界需要注意的一种情况是起点本身就是障碍物那么这种情况直接输出 0。从状态转移的角度看障碍格置 0 后其右侧和下方的合法格子在累加时自然会把经过障碍的路径排除在外因此只需在转移前做一次判空即可无需单独剪枝。Go 实现逐段解析仓库中的标准实现位于 leetcode/0063.Unique-Paths-II/63. Unique Paths II.go函数签名为uniquePathsWithObstacles(obstacleGrid [][]int) int。下面按代码执行顺序逐段解读func uniquePathsWithObstacles(obstacleGrid [][]int) int { // 1. 边界判空网格为空或起点 (0,0) 就是障碍物路径数直接为 0 if len(obstacleGrid) 0 || obstacleGrid[0][0] 1 { return 0 } m, n : len(obstacleGrid), len(obstacleGrid[0]) // 2. 初始化 m x n 的二维 DP 表默认值全部为 0 dp : make([][]int, m) for i : 0; i m; i { dp[i] make([]int, n) } dp[0][0] 1 // 3. 首行初始化只有左侧格子可达 且 本格不是障碍时 dp[0][i] 才为 1 for i : 1; i n; i { if dp[0][i-1] ! 0 obstacleGrid[0][i] ! 1 { dp[0][i] 1 } } // 4. 首列初始化只有上方格子可达 且 本格不是障碍时 dp[i][0] 才为 1 for i : 1; i m; i { if dp[i-1][0] ! 0 obstacleGrid[i][0] ! 1 { dp[i][0] 1 } } // 5. 填表非障碍格 上方方案数 左方方案数 for i : 1; i m; i { for j : 1; j n; j { if obstacleGrid[i][j] ! 1 { dp[i][j] dp[i-1][j] dp[i][j-1] } } } // 6. 返回右下角的路径数 return dp[m-1][n-1] }几个关键设计点值得注意障碍格保持 0代码并未显式写dp[i][j] 0而是依赖make分配的默认零值——只有非障碍格才会被赋值障碍格自然保持 0。这正是题解文档中障碍物的处理方法是dp[i][j]0的实现形态。首行/首列的传播截断与第 62 题首行首列恒为 1不同这里的初始化多了一个前提条件dp[0][i-1] ! 0。含义是一旦首行或首列某个位置被障碍物堵住其右侧下方的所有格子在首行首列上就都不可达。例如首行为[0,0,1,0]时索引 3 的格子虽非障碍却因为左侧被堵而保持dp[0][3] 0。起点判断放在最前obstacleGrid[0][0] 1时立即返回 0避免了后续初始化逻辑在起点为障碍时产生错误值dp[0][0]不会被赋 1但显式早退更符合起点即障碍则无路径的语义。空网格防御len(obstacleGrid) 0的分支保证对空切片访问obstacleGrid[0][0]前已完成判断防止越界 panic。由于转移方程dp[i][j] dp[i-1][j] dp[i][j-1]只依赖上一行与同一行的前一列从源码结构看该实现存在进一步优化空间例如可以只保留一维数组空间 O(n)滚动更新但仓库当前提交保持了二维 DP 表的可读性便于与题目文档对照。测试用例与验证仓库为每题配套独立测试文件第 63 题的测试位于 leetcode/0063.Unique-Paths-II/63. Unique Paths II_test.go函数Test_Problem63通过para63参数/ans63期望答案结构体组织数据驱动式用例共覆盖 5 个场景用例网格期望输出考察点1[[0,0,0],[0,1,0],[0,0,0]]2题目标准示例中心障碍绕行2[[0,0],[1,1],[0,0]]0第二列整体被障碍堵死3[[0,1,0,0],[1,0,0,0],[0,0,0,0]]0首行与首列同时出现障碍路径被完全切断4[][]int{}空网格0空输入防御分支5[[1,0],[0,0]]0起点即障碍直接返回 0测试中若实际值与期望不符会调用t.Fatalf中断并打印输入、期望值和实际值因此用例 4、5 分别验证了实现中len(obstacleGrid) 0与obstacleGrid[0][0] 1两个早退分支。在仓库根目录下可以按如下方式运行该题测试仓库 go.mod 声明go 1.19需相应版本或更高# 只运行第 63 题所在目录的测试 go test ./leetcode/0063.Unique-Paths-II/ -run Test_Problem63 -v # 运行全部题解测试与仓库 gotest.sh 的测试范围一致 go test ./leetcode/...仓库还提供了一个 gotest.sh 脚本其作用是以-covermodeatomic -coverprofilecoverage.txt一次性对./leetcode/...生成合法的单一覆盖率文件供 Codecov 解析——这解释了仓库根目录 coverage.txt 的由来。复杂度分析时间复杂度填表阶段对m x n的每个非边界格子做 O(1) 的加法转移首行首列初始化合计 O(m n)总体为O(m * n)。题目限定m、n最大 100即最多约 10^4 次转移开销很小。空间复杂度当前实现额外分配了一个m x n的 DP 表即O(m * n)。相关仓库文件索引题解文档英文0063.Unique-Paths-II.md题解文档中文0063.Unique-Paths-II/README.md标准解法源码63. Unique Paths II.go单元测试63. Unique Paths II_test.go前置题目无障碍版62. Unique Paths.go测试与覆盖率脚本gotest.sh【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考