34. Unique Paths II

読了目安約2分

DP / LeetCode 63 (Medium) — 障害物のある格子の経路数。DP の初期条件に注意。

この章の目次

問題

LeetCode 63. Unique Paths II（Medium / カテゴリ: DP）

Unique Paths と同じ格子で、今回は一部のマスに障害物があります。格子は 0（通れる）と 1（障害物）の 2 次元配列で与えられます。右か下だけに動いて、左上から右下へ到達する経路数を返してください。スタートやゴールが障害物のこともあります。

考え方

ヒント 1

状態は前問と同じ dp[i][j] = 「マス (i, j) に到達する経路の数」です。障害物のマスは通れないので、到達経路数を 0 として扱います。

ヒント 2

遷移は、障害物なら dp[i][j] = 0、それ以外は上と左の和です。初期条件は「スタートが障害物でなければ dp[0][0] = 1」だけにします。最上行・最左列も「上と左（範囲外は 0）の和」の一般式で処理すると、手前に障害物がある場合も正しく 0 になります。

Swift 実装のポイント

前問のように初期値 1 で埋める書き方は使えません。0 で作り、dp[0][0] だけ立てます。
範囲外参照は i > 0 ? dp[i - 1][j] : 0 の三項演算子で防ぎます。
行数・列数は obstacleGrid.count と obstacleGrid[0].count で取ります。

模範解答

Swift
class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        let m = obstacleGrid.count
        let n = obstacleGrid[0].count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        for i in 0..<m {
            for j in 0..<n {
                if obstacleGrid[i][j] == 1 { continue }
                if i == 0 && j == 0 {
                    dp[0][0] = 1
                    continue
                }
                let fromUp = i > 0 ? dp[i - 1][j] : 0
                let fromLeft = j > 0 ? dp[i][j - 1] : 0
                dp[i][j] = fromUp + fromLeft
            }
        }
        return dp[m - 1][n - 1]
    }
}

計算量: O(mn)。