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()
}