---
title: "213. House Robber II"
url: "https://laigary.com/interview/coding/213-house-robber-ii"
type: "note"
section: "coding"
date: "2023-01-28"
updated: "2026-07-26"
tags: ["Dynamic Programming", "Classic"]
---

# 213. House Robber II

[213\. House Robber II](https://leetcode.com/problems/house-robber-ii/)

和 [198. House Robber](/interview/coding/198-house-robber) 一樣不能偷相鄰的房子，但這次房子排成一個**環** —— 第一間和最後一間也是相鄰的。

## 思路

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

### 為什麼可以拆成兩次直線

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

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

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

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

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

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

### 邊界

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

## 解題方向

```python
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)$ 空間可以改成傳起訖索引：

```python
    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](/interview/coding/198-house-robber) | 一排 | 陣列上相鄰 | 一維 DP |
| **213 這題** | 一**環** | 首尾也相鄰 | **拆成兩條直線各跑一次** |
| [337. House Robber III](/interview/coding/337-house-robber-iii) | 一棵**樹** | 父子相鄰 | 後序遞迴，回傳兩個狀態 |
| [740. Delete and Earn](/interview/coding/740-delete-and-earn) | 一排（按**數值**） | 數值差 1 | 先轉換，再套 198 |

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

整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)。

## 複雜度

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

其中 `n` 是房子數量。

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