63. Unique Paths II

Medium

Description

給定一個 m x n 的網格，其中 1 代表障礙物，0 代表可通行。機器人從左上角出發，每次只能往右或往下移動，求到達右下角共有多少條不同路徑。

Example:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2

Intuition#

與 Unique Paths 相同，但遇到障礙物的格子路徑數為 0。

延續 62 題的 DP 思路，差別在於若 obstacleGrid[i][j] == 1，則 dp[i][j] = 0
起點或終點若是障礙物，直接回傳 0
第一行/第一列遇到障礙物後，後面全為 0

Approaches#

1: 2D DP Table#

概念: 建立 m x n 的 DP 表格，遇到障礙物就設為 0，否則 dp[i][j] = dp[i-1][j] + dp[i][j-1]
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0

        val dp = Array(m) { IntArray(n) }
        dp[0][0] = 1
        for (i in 1 until m) dp[i][0] = if (obstacleGrid[i][0] == 1) 0 else dp[i - 1][0]
        for (j in 1 until n) dp[0][j] = if (obstacleGrid[0][j] == 1) 0 else dp[0][j - 1]

        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = if (obstacleGrid[i][j] == 1) 0 else dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }
}

⭐2: 1D DP（空間優化）#

概念: 用一維陣列滾動更新，遇到障礙物時設為 0，否則累加左方值。
時間複雜度: O(m * n)
空間複雜度: O(n)

class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val n = obstacleGrid[0].size
        val dp = IntArray(n)
        dp[0] = 1

        for (row in obstacleGrid) {
            for (j in 0 until n) {
                if (row[j] == 1) {
                    dp[j] = 0
                } else if (j > 0) {
                    dp[j] += dp[j - 1]
                }
            }
        }
        return dp[n - 1]
    }
}

🔑 Takeaways#

Pattern: 網格型 DP 加上障礙物條件判斷
關鍵技巧: 障礙物格子的 DP 值直接設為 0，其餘邏輯與 62 題一致；1D 空間優化同樣適用