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

# 198. House Robber

[198. House Robber](https://leetcode.com/problems/house-robber/)

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

## 思路

這題是「選或不選」型 DP 的原型，整個家族（[213](/interview/coding/213-house-robber-ii)、[337](/interview/coding/337-house-robber-iii)、[740](/interview/coding/740-delete-and-earn)）都是它的變形，所以值得把狀態定義講到很清楚。

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

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

兩者取大就是答案：

$$f(i) = \max\bigl(f(i+1),\; nums[i] + f(i+2)\bigr)$$

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

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

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

## 解題方向

### 自頂向下

```python
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 面試技巧](/interview/coding/python-tips-for-interview)。

### 自底向上

```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)$：轉移只用到前兩格，所以兩個變數就夠：

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

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

## 補充

**整個家族**：


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


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

**同一個遞推結構的還有** [70. Climbing Stairs](/interview/coding/70-climbing-stairs)（也是 `f(n)` 只依賴前兩項），差別只在一個取 `max`、一個取和。整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)。

## 複雜度

**自頂向下（記憶化遞迴）**

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

**自底向上**

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

其中 `n` 是房子數量。