33. Unique Paths

読了目安 約1分

DP / LeetCode 62 (Medium) — 格子上の経路数を 2 次元 DP で数える。

問題

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

m 行 n 列の格子があり、ロボットが左上のマスにいます。 ロボットは右か下にしか動けません。 右下のマスに到達する経路が何通りあるかを返してください。 m と n はそれぞれ 100 以下です。

考え方

Swift 実装のポイント

• 2 次元配列は [[Int]](repeating: [Int](repeating: 1, count: n), count: m) で作ります。初期値を 1 にすると、最上行・最左列の初期条件が同時に済みます。
• m == 1 や n == 1 のとき 1..<1 は空範囲になり、ループは 1 回も回りません（実行時エラーにはなりません）。
• 遷移が直前の行しか見ないので、1 行分の配列を使い回せば空間 O(n) にできます。

class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var dp = [[Int]](repeating: [Int](repeating: 1, count: n), count: m)
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }
}