【华为机试】63. 不同路径 II

63. 不同路径 II

题目描述

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

解题思路

核心思想：动态规划（避开障碍）

与“接雨水”一样，本题也可通过多种思路来解决，但最优且主流的做法是动态规划。定义 dp[i][j] 为从起点 (0,0) 走到 (i,j) 的不同路径数：

• 若 (i,j) 为障碍（值为1）：dp[i][j] = 0
• 否则：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方到达）

初始条件：

• 若起点或终点是障碍，则答案为 0
• dp[0][0] = 1（前提：起点无障碍）

算法流程

graph TDA[开始] --> B[输入 obstacleGrid]B --> C{起点/终点是否为障碍}C -->|是| D[返回 0]C -->|否| E[初始化 dp]E --> F[按行填表]F --> G{遇到障碍?}G -->|是| H[置 0]G -->|否| I[dp[i][j]=dp[i-1][j]+dp[i][j-1]]H --> FI --> FF --> J[返回 dp[m-1][n-1]]

复杂度分析

• 时间复杂度：O(m·n)
• 空间复杂度：
  • 二维 DP：O(m·n)
  • 一维DP（空间优化）：O(n)

边界与细节

• 起点或终点为障碍：直接返回 0
• 首行/首列初始化时，若遇到障碍，其后全部为 0
• 一维 DP 时，遇到障碍位置要将 dp[j] 置 0

方法对比

graph TDA[方法对比] --> B[二维DP]A --> C[一维DP]A --> D[记忆化DFS]B --> E[易理解 空间O(mn)]C --> F[最优空间 O(n)]D --> G[实现直观 递归栈]

代码实现

Go 实现（含二维DP / 一维DP / 记忆化）

package mainimport ("fmt"
)func uniquePathsWithObstaclesDP2D(obstacleGrid [][]int) int { /* 见 main.go */ return 0 }
func uniquePathsWithObstaclesDP1D(obstacleGrid [][]int) int { /* 见 main.go */ return 0 }
func uniquePathsWithObstaclesMemo(obstacleGrid [][]int) int { /* 见 main.go */ return 0 }func main() {grid := [][]int{{0,0,0},{0,1,0},{0,0,0}}fmt.Println(uniquePathsWithObstaclesDP1D(grid)) // 输出: 2
}

完整可运行代码与测试见 main.go。

测试用例设计

建议覆盖：

• 起点/终点为障碍
• 单行、单列、1x1
• 中间若干障碍导致路径阻断
• 无障碍的普通网格

小结

• 本题的本质是“有障碍的网格路径计数”，动态规划最稳妥
• 一维 DP 可在不影响可读性的情况下，将空间优化到 O(n)
• 记忆化搜索更贴近推导，便于理解转移关系

完整题解代码

package mainimport ("fmt""strings""time"
)// 解法一：二维动态规划（直观）
// 状态定义：
//
//	dp[i][j] 表示到达单元格 (i, j) 的不同路径数
//
// 状态转移：
//
//	若 obstacleGrid[i][j] 为障碍(1)，则 dp[i][j] = 0
//	否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]（来自上方和左方）
//
// 初始条件：
//
//	dp[0][0] = 1（前提是 obstacleGrid[0][0] == 0）
//
// 答案：
//
//	dp[m-1][n-1]
func uniquePathsWithObstaclesDP2D(obstacleGrid [][]int) int {m := len(obstacleGrid)if m == 0 {return 0}n := len(obstacleGrid[0])if n == 0 {return 0}if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {return 0}dp := make([][]int, m)for i := 0; i < m; i++ {dp[i] = make([]int, n)}dp[0][0] = 1// 初始化首行for j := 1; j < n; j++ {if obstacleGrid[0][j] == 1 {dp[0][j] = 0} else {dp[0][j] = dp[0][j-1]}}// 初始化首列for i := 1; i < m; i++ {if obstacleGrid[i][0] == 1 {dp[i][0] = 0} else {dp[i][0] = dp[i-1][0]}}// 填表for i := 1; i < m; i++ {for j := 1; j < n; j++ {if obstacleGrid[i][j] == 1 {dp[i][j] = 0continue}dp[i][j] = dp[i-1][j] + dp[i][j-1]}}return dp[m-1][n-1]
}// 解法二：一维动态规划（空间优化到 O(n)）
// 复用一行 dp：dp[j] 表示当前行列 j 的到达路径数
// 当遇到障碍时将 dp[j] 置 0；否则 dp[j] += dp[j-1]
func uniquePathsWithObstaclesDP1D(obstacleGrid [][]int) int {m := len(obstacleGrid)if m == 0 {return 0}n := len(obstacleGrid[0])if n == 0 {return 0}if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {return 0}dp := make([]int, n)dp[0] = 1for i := 0; i < m; i++ {for j := 0; j < n; j++ {if obstacleGrid[i][j] == 1 {dp[j] = 0} else if j > 0 {dp[j] += dp[j-1]}}}return dp[n-1]
}// 解法三：记忆化搜索（自顶向下）
// 注意：在最坏情况下与 DP 等价，但实现上更贴近转移关系
func uniquePathsWithObstaclesMemo(obstacleGrid [][]int) int {m := len(obstacleGrid)if m == 0 {return 0}n := len(obstacleGrid[0])if n == 0 {return 0}if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {return 0}memo := make([][]int, m)for i := 0; i < m; i++ {memo[i] = make([]int, n)for j := 0; j < n; j++ {memo[i][j] = -1}}var dfs func(i, j int) intdfs = func(i, j int) int {if i < 0 || j < 0 {return 0}if obstacleGrid[i][j] == 1 {return 0}if i == 0 && j == 0 {return 1}if memo[i][j] != -1 {return memo[i][j]}memo[i][j] = dfs(i-1, j) + dfs(i, j-1)return memo[i][j]}return dfs(m-1, n-1)
}// 辅助：对比多个算法的结果，确保一致性
func runTestCases() {type testCase struct {grid     [][]intexpected intdesc     string}tests := []testCase{{[][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 2, "示例1：中间有障碍"},{[][]int{{0, 1}, {0, 0}}, 1, "示例2：两行两列"},{[][]int{{0}}, 1, "1x1 无障碍"},{[][]int{{1}}, 0, "1x1 有障碍"},{[][]int{{0, 0, 0, 0}}, 1, "单行无障碍"},{[][]int{{0, 1, 0, 0}}, 0, "单行有障碍阻断"},{[][]int{{0}, {0}, {0}}, 1, "单列无障碍"},{[][]int{{0}, {1}, {0}}, 0, "单列有障碍阻断"},{[][]int{{0, 0}, {1, 0}}, 1, "简单障碍-右下可达"},{[][]int{{0, 0}, {0, 1}}, 0, "终点为障碍"},{[][]int{{1, 0}, {0, 0}}, 0, "起点为障碍"},}fmt.Println("=== 63. 不同路径 II - 测试 ===")for i, tc := range tests {r1 := uniquePathsWithObstaclesDP2D(cloneGrid(tc.grid))r2 := uniquePathsWithObstaclesDP1D(cloneGrid(tc.grid))r3 := uniquePathsWithObstaclesMemo(cloneGrid(tc.grid))ok := (r1 == tc.expected) && (r2 == tc.expected) && (r3 == tc.expected)status := "✅"if !ok {status = "❌"}fmt.Printf("用例 %d: %s\n", i+1, tc.desc)fmt.Printf("输入: %v\n", tc.grid)fmt.Printf("期望: %d\n", tc.expected)fmt.Printf("二维DP: %d, 一维DP: %d, 记忆化: %d\n", r1, r2, r3)fmt.Printf("结果: %s\n", status)fmt.Println(strings.Repeat("-", 40))}
}// 简单性能比较
func benchmark() {fmt.Println("\n=== 性能对比（粗略） ===")big := make([][]int, 100)for i := range big {big[i] = make([]int, 100)}start := time.Now()_ = uniquePathsWithObstaclesDP2D(big)d1 := time.Since(start)start = time.Now()_ = uniquePathsWithObstaclesDP1D(big)d2 := time.Since(start)start = time.Now()_ = uniquePathsWithObstaclesMemo(big)d3 := time.Since(start)fmt.Printf("二维DP: %v\n", d1)fmt.Printf("一维DP: %v\n", d2)fmt.Printf("记忆化: %v\n", d3)
}func cloneGrid(g [][]int) [][]int {m := len(g)res := make([][]int, m)for i := 0; i < m; i++ {res[i] = append([]int(nil), g[i]...)}return res
}func main() {fmt.Println("63. 不同路径 II")fmt.Println(strings.Repeat("=", 40))runTestCases()benchmark()
}