35. House Robber

読了目安約1分

DP / LeetCode 198 (Medium) — 隣り合う家を選べない条件での最大金額。取る・取らないの DP。

この章の目次

問題

LeetCode 198. House Robber（Medium / カテゴリ: DP）

一列に並んだ家があり、nums[i] は i 番目の家にある金額です。隣り合う 2 軒から盗むと警報が鳴るため、選ぶ家は隣接してはいけません。盗める金額の最大値を返してください。

考え方

ヒント 1

状態を dp[i] = 「先頭から i 軒目までを対象にしたときの最大金額」と定めます。各家は「盗む」か「盗まない」の 2 択です。

ヒント 2

i 軒目を盗むなら 1 つ手前は使えないので dp[i-2] + nums[i]、盗まないなら dp[i-1] です。遷移は dp[i] = max(dp[i-1], dp[i-2] + nums[i])。初期条件は「0 軒までの最大 = 0」で、直前 2 つの値だけ持てば十分です。

Swift 実装のポイント

dp 配列を作らず、変数 2 つ（2 軒前までの最大 prev と 1 軒前までの最大 cur）で回せます。
(prev, cur) = (cur, max(cur, prev + x)) のタプル代入で、2 変数を一時変数なしに同時更新できます。
初期値は両方 0 にします。要素 1 個の配列でも正しく動きます。

模範解答

Swift
class Solution {
    func rob(_ nums: [Int]) -> Int {
        var prev = 0
        var cur = 0
        for x in nums {
            (prev, cur) = (cur, max(cur, prev + x))
        }
        return cur
    }
}

計算量: O(N)。