198. House Robber

──────────────────────────────────────────────────────────────────────

198. House Robber

一排房子各有金額，不能偷相鄰的兩間，問最多能偷多少。

思路

這題是「選或不選」型 DP 的原型，整個家族（213、337、740）都是它的變形，所以值得把狀態定義講到很清楚。

站在第 i 間房子前面，只有兩個選擇：

偷它 → 拿到 nums[i]，但下一間不能碰，所以接下來從 i + 2 開始
不偷 → 什麼都沒拿，接下來從 i + 1 開始

兩者取大就是答案：

$f (i) = \max (f (i + 1), n u m s [i] + f (i + 2))$

這裡的 f(i) 定義是「從第 i 間開始往後，最多能偷多少」。 定義一旦說清楚，base case 就自動出來了：i 超出範圍時沒東西可偷，回傳 0。

面試時把這句「f(i) 代表什麼」講出來，比急著寫程式碼重要得多 —— 大多數人卡住不是不會遞迴，是沒定義清楚狀態就開始寫。

為什麼不用「上一間有沒有偷」當狀態？ 也可以，那會變成 f(i, 有沒有偷上一間) 兩個狀態。但這題不需要 —— 因為「偷了 i 就跳到 i+2」已經隱含了那個限制，用一維就夠。

解題方向

自頂向下

class Solution:
    def rob(self, nums: List[int]) -> int:  
        @cache
        def dp(index):
            if index >= len(nums):
                return 0
            return max(dp(index + 1), dp(index + 2) + nums[index])
            
        return dp(0)

這版和上面的遞迴式一行一行對得起來，所以是最好想的寫法：先寫暴力遞迴，再加 memo。用 functools.cache 裝飾器也可以省掉手寫的 memo 字典，見 Python 面試技巧。

自底向上

class Solution:
    def rob(self, nums: List[int]) -> int:  
        memo = [0] * (len(nums) + 1)
        memo[0] = 0
        memo[1] = nums[0]

        for i in range(2, len(memo)):
            num = nums[i-1]
            memo[i] = max(memo[i-1], memo[i-2] + num)

        return memo[-1]

注意這版的 memo 比 nums 長一格，而且方向反過來 —— memo[i] 是「前 i 間房子的最佳解」，不是「從第 i 間開始」。所以裡面要用 nums[i-1] 取值，索引差一。

這種「dp 陣列多一格當虛擬起點」的寫法可以讓 base case 變得很乾淨（memo[0] = 0 表示沒有房子時偷 0），代價是要一直記得 nums[i-1] 的偏移。兩種索引慣例（f(i) 從 i 開始 vs dp[i] 前 i 個）不要混用，選定一種寫到底。

空間可以降到 $O (1)$ ：轉移只用到前兩格，所以兩個變數就夠：

        prev, curr = 0, 0
        for num in nums:
            prev, curr = curr, max(curr, prev + num)
        return curr

這也是這題最常見的面試最佳解。

補充

整個家族：

題目	排列方式	「相鄰」是什麼	解法
198 這題	一排	陣列上相鄰	一維 DP
213. House Robber II	一環	首尾也相鄰	拆成兩條直線各跑一次
337. House Robber III	一棵樹	父子相鄰	後序遞迴，回傳 (偷, 不偷) 兩個值
740. Delete and Earn	一排（按數值）	數值差 1	先轉換，再套 198

740 特別值得注意 —— 它表面上完全是另一題，但把「刪掉 x 就不能留 x-1 和 x+1」轉換成「按數值排一排、不能取相鄰」之後就是本題。看到「不能同時選相鄰的兩個」就要想到這裡。

同一個遞推結構的還有 70. Climbing Stairs（也是 f(n) 只依賴前兩項），差別只在一個取 max、一個取和。整理見 Dynamic Programming 模板。

複雜度

自頂向下（記憶化遞迴）

時間 $O (n)$ — 每個 index 只算一次，之後都命中 memo
空間 $O (n)$ — memo 字典加上遞迴堆疊

自底向上

時間 $O (n)$ — 一個迴圈
空間 $O (n)$ — dp 陣列；用滾動變數可以降到 $O (1)$

其中 n 是房子數量。