LeetCode-Go 动态规划实战：用 Go 实现带障碍物的路径计数（Unique Paths II，第 63 题）-育师

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.md）：

Input: [ [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 脚本，其作用是以-covermode=atomic -coverprofile=coverage.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)。