House Robber
題目描述
給定一個非負整數陣列 nums，代表每棟房子的金額。不能偷相鄰兩棟，回傳能偷到的最大金額。
輸入：nums = [1,2,3,1]
輸出：4
解釋：偷第 0 棟(1) + 第 2 棟(3) = 4
輸入：nums = [2,7,9,3,1]
輸出：12
解釋：偷第 0 棟(2) + 第 2 棟(9) + 第 4 棟(1) = 12
解題思路
定義狀態
dp[i] = 考慮前 i 棟房子（index 0 到 i-1）能偷到的最大金額
轉移方程
dp[i] = max(dp[i-1], dp[i-2] + nums[i])。以 [2,7,9,3,1] 為例：dp[2] = max(7, 0+9) = 9
偷 or 不偷
不偷第 i 棟 → 收益等於 dp[i-1]（跟沒有第 i 棟一樣）；偷第 i 棟 → 跳過 i-1，收益 = dp[i-2] + nums[i]
空間優化
dp[i] 只依賴 dp[i-1] 和 dp[i-2]，用 prev1 和 prev2 兩個變數滾動，省下整個 dp 陣列
程式碼
C#
public class Solution {
public int Rob(int[] nums) {
if (nums.Length == 1) return nums[0];
int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]
foreach (int num in nums) {
int curr = Math.Max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}TypeScript
function rob(nums: number[]): number {
let prev2 = 0; // 前前棟的最大收益
let prev1 = 0; // 前一棟的最大收益
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Python
def rob(nums: list[int]) -> int:
prev2, prev1 = 0, 0 # dp[i-2], dp[i-1]
for num in nums:
curr = max(prev1, prev2 + num)
prev2, prev1 = prev1, curr
return prev1複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
- Time：線性遍歷一次 nums，每步只做一次 max 和兩次賦值
- Space：兩個滾動變數 prev1 和 prev2 取代 dp 陣列
圖解
圖表展示了最佳偷竊路線：選房子 0($2)→跳過 1→選 2($9)→跳過 3→選 4($1)，總計 $12。 注意不一定總是「隔一棟偷一棟」——有時跳過兩棟更划算（取決於具體金額）。
進階觀點
💡面試追問
Q: House Robber II（環形）怎麼解？ A: 第一棟和最後一棟相鄰，不能同時偷。解法：跑兩次 House Robber I，一次排除第一棟（nums[1..n-1]），一次排除最後一棟（nums[0..n-2]），取兩次結果的較大值。因為第一棟和最後一棟不可能同時被偷，兩次計算覆蓋了所有合法方案。
Q: House Robber III（樹形）怎麼解？ A: 房子排成二叉樹，每個節點回傳兩個值：(偷自己的最大值, 不偷自己的最大值)。父節點偷自己則子節點不能偷，反之子節點可偷可不偷。用後序遍歷（bottom-up）從葉子往上計算。
Q: 轉移方程的通用性？
A: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 是「取或不取」的經典範本。任何「不能選相鄰元素」的最大化問題都能用這個框架：股票交易冷卻期、顏色塗漆（Paint House）、刪除與獲得（Delete and Earn）等。
邊界情況
- 只有一棟房子：直接回傳 nums[0]，沒有鄰居限制
- 只有兩棟房子：回傳 max(nums[0], nums[1])，只能偷其中一棟
- 所有房子金額相同：最佳策略是偷所有奇數位或偶數位，答案 = ceil(n/2) × 金額
理解測驗
🤔 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 中，dp[i-1] 代表什麼？
🤔 為什麼偷第 i 棟時要加 dp[i-2] 而不是 dp[i-1]？