動態規劃解決LeetCode 63題：不同路徑 II（含障礙物）

1. 題目鏈接

LeetCode 63. 不同路徑 II

2. 題目描述

一個機器人位于 m x n 網格的左上角，每次只能向右或向下移動一步。網格中可能存在障礙物（標記為 1），機器人不能經過障礙物。求從左上角到右下角的不同路徑總數。

示例 1：
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：存在障礙物在中心位置，兩條路徑為：

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

示例 2：
輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1

3. 示例分析

以 示例 1 的輸入為例：

• 機器人需要繞過中心的障礙物。
• 動態規劃表 dp 在計算時會跳過障礙物位置，最終右下角的值為 2。

4. 算法思路

動態規劃狀態定義

• dp[i][j] 表示到達網格 (i-1, j-1) 位置的有效路徑數（i 和 j 從 1 開始，避免越界）。

狀態轉移方程

• 若 (i-1, j-1) 是障礙物，dp[i][j] = 0（無法到達）。
• 否則，dp[i][j] = dp[i-1][j] + dp[i][j-1]。

初始化技巧

• 初始化 dp[0][1] = 1，使得 dp[1][1] 可以正確推導初始值，無需單獨處理第一行和第一列。

5. 邊界條件與注意事項

1. 起點或終點為障礙物：直接返回 0。
2. 單行或單列網格：若路徑中存在障礙物，路徑數為 0。
3. 障礙物處理：遍歷時需跳過障礙物位置，保持 dp[i][j] = 0。

6. 代碼實現（修正版）

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();// 起點或終點是障礙物，直接返回0if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));dp[0][1] = 1; // 初始化虛擬起點for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 跳過障礙物位置if (obstacleGrid[i-1][j-1] == 0) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}}return dp[m][n];}
};

代碼解析

1. 提前檢查障礙物：若起點或終點是障礙物，直接返回 0，避免無效計算。
2. 動態規劃表填充：遍歷時跳過障礙物位置，保證路徑數不會累加無效值。
3. 返回值：dp[m][n] 表示到達右下角的有效路徑總數。

---

時間復雜度：O(mn)，空間復雜度：O(mn)。通過動態規劃表逐格計算，高效處理含障礙物的路徑問題。