198. 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。

這個問題的核心思想是動態規劃。我們可以將問題分解為子問題：

• 對于每個房子?i，我們有兩種選擇：偷或不偷。
• 如果我們偷了第?i?個房子，那么我們不能偷第?i-1?個房子，所以最大金額是?dfs(i - 2) + nums[i]。
• 如果我們不偷第?i?個房子，那么最大金額是?dfs(i - 1)。
• 我們取這兩種選擇中的最大值作為?dfs(i)?的結果。

?下面關于這道題目的具體題解，思路和之前的爬樓梯題目解題思路一致，建議先看完這篇文檔再來繼續食用哦~~

動態規劃題解——爬樓梯【LeetCode】三種方法_動態規劃 爬樓梯-CSDN博客

---

一、算法邏輯（每一步思路）

? 問題描述：

給定一個整數數組 nums，每個元素表示某一間房屋中的金額。相鄰的房屋不能被同時偷盜，問最多可以偷多少錢。

---

? 解題思路（DP 狀態定義與轉移）

1. 狀態定義：

設：

• f0 表示「不偷當前這家時的最大收益」；
• f1 表示「偷當前這家時的最大收益」。

隨著遍歷每一間房，我們動態更新這兩個變量。

2. 狀態轉移邏輯：

對于當前房屋金額 x：

• 如果我們偷它，就不能偷上一個：f1 = f0 + x
• 如果我們不偷它，就保留上一個偷的最大值：f1 = max(f1, f0 + x)
• 所以前一步狀態要滾動更新：先將 f0 = f1，然后用前一個 f0 + x 計算新的 f1

總結起來為：

f0, f1 = f1, max(f1, f0 + x)

3. 初始化：

• 初始時 f0 = f1 = 0，表示沒偷任何房屋；
• 隨著每個房間的遍歷進行動態更新。

4. 最終返回結果：

• f1 就是最終的最大收益（在遍歷結束后，無論最后一間偷還是不偷都已被計算）。

---

二、算法核心點

? 核心思想：動態規劃 + 狀態滾動

• 對于每一間房子都有兩種選擇：偷或不偷；
• 關鍵是不能偷相鄰的兩家，因此形成狀態遞推結構；
• 用兩個變量 f0、f1 取代整個數組，進行滾動優化。

class Solution:def rob(self, nums: List[int]) -> int:f0 = f1 = 0for x in nums:f0, f1 = f1, max(f1, f0 + x)return f1

---

三、復雜度分析

• 時間復雜度：O(n)

• • 遍歷數組一遍。

• 空間復雜度：O(1)

• • 只用了兩個變量（而不是數組），空間極致優化。

---

總結表

維度	內容
? 思路邏輯	每間房子選擇“偷”或“不偷”，根據前一個狀態遞推最大金額
? 核心技巧	動態規劃 + 狀態滾動優化（用 f0, f1 代替 dp 數組）
? 時間復雜度	O(n)
? 空間復雜度	O(1)

---

? 舉個例子說明

輸入：

nums = [2, 7, 9, 3, 1]

狀態變化：

初始: f0 = 0, f1 = 0
遍歷 2: f0 = 0, f1 = max(0, 0 + 2) = 2
遍歷 7: f0 = 2, f1 = max(2, 0 + 7) = 7
遍歷 9: f0 = 7, f1 = max(7, 2 + 9) = 11
遍歷 3: f0 = 11, f1 = max(11, 7 + 3) = 11
遍歷 1: f0 = 11, f1 = max(11, 11 + 1) = 12

最終返回 f1 = 12