📘 題目敘述
你是一個專業小偷，計畫沿著一條街偷房子。每間房子都藏有一定金額，唯一的限制是：相鄰的房子有連動的保全系統，如果同一個晚上有兩間相鄰房子都被闖入，系統就會自動報警。
給你一個整數陣列 nums，其中 nums[i] 代表第 i 間房子裡的金額。請回傳你今晚在不觸發警報的情況下，能偷到的最大金額。
條件限制
1 <= nums.length <= 1000 <= nums[i] <= 400
🧠 解題思路
這題是典型的 DP：每一間房子只有「偷」或「不偷」兩種狀態，而且「偷第 i 間」會影響到「第 i-1 間不能偷」。
所以我把狀態拆成兩個 DP 陣列，讓邏輯跟程式碼對得上：
dp0[i]：走到第i間時，第 i 間不偷 的最大金額dp1[i]：走到第i間時，第 i 間有偷 的最大金額
有了這兩個狀態後，轉移就很直覺：
- 如果第
i間不偷：那我只要承接前一間「偷或不偷」的最大值即可
dp0[i] = max(dp0[i-1], dp1[i-1]) - 如果第
i間要偷：前一間一定不能偷，所以只能從
dp0[i-1]轉移dp1[i] = nums[i] + dp0[i-1]
最後答案就是最後一間偷或不偷的最大值。
所有變數
n：房子數量（nums.size()）dp0：dp0[i]表示走到第i間且第i間不偷時的最大金額dp1：dp1[i]表示走到第i間且第i間有偷時的最大金額
🪜 主要流程步驟
1. 初始化第 0 間房子的兩種狀態
第 0 間只有兩種情況：
- 不偷：
dp0[0] = 0 - 偷：
dp1[0] = nums[0]
2. 依序處理第 1 間到第 n-1 間
對每個 i >= 1：
先算「不偷第 i 間」：
dp0[i] = max(dp0[i - 1], dp1[i - 1])
意思是：第 i 間不偷，我就沿用前一間最好的結果（前一間偷或不偷都可以）。
再算「偷第 i 間」：
dp1[i] = nums[i] + dp0[i - 1]
意思是：第 i 間要偷，前一間一定要不偷，所以只能接 dp0[i-1]。
3. 回傳最後一間的最大值
最後答案就是：
max(dp0[n - 1], dp1[n - 1])
代表最後一間偷或不偷都考慮進去，取最大。
⏱️ 複雜度
- 時間複雜度：
O(n)
只掃一次房子。 - 空間複雜度：
O(n)
兩個 DP 陣列各長度n。
💻 程式碼實作
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp0(n); // 沒選
vector<int> dp1(n); // 有選
dp0[0] = 0;
dp1[0] = nums[0];
for (int i = 1; i < n; i++) {
dp0[i] = max(dp0[i - 1], dp1[i - 1]);
dp1[i] = nums[i] + dp0[i - 1];
}
return max(dp0[n - 1], dp1[n - 1]);
}
};
🔗 題目連結
https://leetcode.com/problems/house-robber/