198. House Robber

Medium

Description

一排房屋各有不同金額，相鄰的房屋不能同時被搶。給定代表每間房屋金額的整數陣列 nums，求在不觸發警報的情況下能搶到的最大金額。

Example:

Input: nums = [2,7,9,3,1] Output: 12

Intuition#

每間房屋只有兩種選擇：搶或不搶。搶了就跳過下一間，不搶則繼續。

對於第 i 間房屋：搶 → dp[i-2] + nums[i]，不搶 → dp[i-1]
狀態轉移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
經典的「取或不取」DP 模式

Approaches#

1: Bottom-Up DP Array#

概念: 建立 DP 陣列紀錄到每間房屋為止的最大收益
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]
        val dp = IntArray(nums.size)
        dp[0] = nums[0]
        dp[1] = maxOf(nums[0], nums[1])
        for (i in 2 until nums.size) {
            dp[i] = maxOf(dp[i - 1], dp[i - 2] + nums[i])
        }
        return dp[nums.size - 1]
    }
}

⭐2: Rolling Variables#

概念: 只需要前兩個狀態，用兩個變數即可
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun rob(nums: IntArray): Int {
        var prev2 = 0
        var prev1 = 0
        for (num in nums) {
            val cur = maxOf(prev1, prev2 + num)
            prev2 = prev1
            prev1 = cur
        }
        return prev1
    }
}

🔑 Takeaways#

Pattern: 取或不取 (Take or Skip) — 每個元素有兩種決策，取了就跳過相鄰元素
關鍵技巧: prev2 代表「不包含前一個」的最大值，prev1 代表「包含或不包含前一個」的最大值