213. House Robber II

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

和 198. House Robber 一樣不能偷相鄰的房子，但這次房子排成一個環 —— 第一間和最後一間也是相鄰的。

思路

基本上先完成 198. House Robber，自頂向下或自底向上都沒關係，接著判斷要不要偷第一家或最後一家，取比較大的值。

為什麼可以拆成兩次直線

環的麻煩在於首尾互相牽制：偷了第一間就不能偷最後一間，反之亦然。直接在環上做 DP 需要多一個狀態記「有沒有偷第一間」，很囉唆。

但換個角度想 —— 在任何一個合法方案裡，第一間和最後一間至少有一間沒被偷（不可能兩間都偷，因為它們相鄰）。於是所有方案必然落在這兩類之一：

不偷最後一間 → 問題退化成在 nums[0 : n-1] 這條直線上做 198
不偷第一間 → 退化成在 nums[1 : n] 這條直線上做 198

兩類的最大值取 max 就是答案。環被拆成了兩條直線，而直線的解法已經會了。

這兩類會不會漏掉「兩間都不偷」的方案？ 不會 —— 那種方案同時屬於這兩類，會被兩邊都算到，取 max 不影響正確性。重疊沒關係，只要涵蓋完整就好，這是這個拆法成立的關鍵。

「環 → 拆成兩條直線」是處理環形 DP 的通用手法，值得記住。

邊界

n <= 2 要特別處理：環上只有兩間房子時它們互為鄰居，只能偷其中較大的那間。直接 max(nums) 就對了。如果不特判，nums[:-1] 會變成只剩一個元素，而 rob_one 裡的 nums[1] 會越界。

解題方向

class Solution:

    def rob_one(self, nums: List[int]) -> int:
        p1 = nums[0]
        p2 = max(p1, nums[1])
        res = max(p1, p2)
        for i in range(2, len(nums)):
            res = max(p2, nums[i] + p1)
            p1 = p2
            p2 = res
        return res

    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)

        t1 = self.rob_one(nums[:-1])
        t2 = self.rob_one(nums[1:])
        return max(t1, t2)

rob_one 就是 198 的滾動變數版：p1 是前兩格的最佳解、p2 是前一格的，res = max(不偷我, 偷我 + 前兩格)。

p2 = max(p1, nums[1]) 這行是在初始化「前兩間的最佳解」—— 兩間房子相鄰，只能取大的那間。

切片會複製陣列，所以 nums[:-1] 和 nums[1:] 各多花 $O (n)$ 空間。要真正的 $O (1)$ 空間可以改成傳起訖索引：

    def rob_range(self, nums, lo, hi):      # 閉區間 [lo, hi]
        p1 = p2 = 0
        for i in range(lo, hi + 1):
            p1, p2 = p2, max(p2, p1 + nums[i])
        return p2

    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        return max(self.rob_range(nums, 0, len(nums) - 2),
                   self.rob_range(nums, 1, len(nums) - 1))

這版的 p1 = p2 = 0 起手也省掉了 n <= 2 的特判 —— 空區間自然回傳 0。

補充

整個家族：

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

「環 → 拆成兩條直線」的其他應用：環形陣列的最大子陣列和、環形加油站問題，思路都是「找出一個必然成立的二分法，把環切開」。

整理見 Dynamic Programming 模板。

複雜度

時間 $O (n)$ — 跑兩次線性 DP， $2 \times O (n)$ 仍是 $O (n)$
空間 $O (n)$ 用切片、 $O (1)$ 用起訖索引的版本

其中 n 是房子數量。

跑兩次不會讓複雜度變差，這點值得主動講 —— 有些人會擔心「拆成兩個子問題會不會變慢」，答案是常數倍而已。