LeetCode 不同路徑 II：動態規劃處理障礙物

題目描述

機器人從左上角走到右下角，只能向右/向下移動。網格中 0 表示通路，1 表示障礙物。求不同路徑數。

範例：

輸入: [[0,0,0],[0,1,0],[0,0,0]]
輸出: 2
路徑: 右→右→下→下、下→下→右→右

解題思路：DP + 障礙判斷

同「不同路徑 I」，但障礙格路徑數為 0：

1. dp[i][j] 表示到達 (i,j) 的路徑數
2. 若 obstacleGrid[i][j] == 1：dp[i][j] = 0
3. 否則：dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. 初始化：起點若是障礙直接返回 0；首行首列遇障礙後全 0

時間複雜度：O(mn)，空間複雜度：O(mn)（可優化至 O(n)）。

Python 參考實現

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if not obstacleGrid or obstacleGrid[0][0] == 1:
            return 0
        
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        
        # 首列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
        # 首行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]]) == 2
    assert sol.uniquePathsWithObstacles([[1]]) == 0
    assert sol.uniquePathsWithObstacles([[0,1],[0,0]]) == 1
    print("所有測試通過")

空間優化：一維 DP O(n)

    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid or obstacleGrid[0][0] == 1:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * n
        dp[0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j-1]
        return dp[-1]

核心要點總結

• 障礙即歸零：dp[i][j] = 0 自然切斷通過該格的所有路徑
• 初始化鏈式：首行首列遇障礙後續全 0，體現「不可達」傳遞
• 一維優化：dp[j] += dp[j-1] 原地更新，障礙處歸零
• 起點檢查：obstacleGrid[0][0] == 1 直接返回 0

不同路徑 II 是網格 DP 入門進階題，在基礎遞推上增加「狀態禁用」邏輯，掌握後可解決「帶陷阱/代價/限制」的網格路徑問題。