主題: 學習筆記

LeetCode 198：打家劫舍，用兩個狀態處理搶與不搶

記錄我的 House Robber 解法，拆解 p1、p2 為什麼可行，再改成狀態定義更清楚的 O(n) 時間、O(1) 額外空間版本。

這題延續了 Climbing Stairs 的一維動態規劃，但狀態之間的關係不再是單純相加。每走到一間房屋，我都要在「不搶這間」和「搶這間」之間選一個比較好的結果。

我在卡住時取得一層概念提示：把每間房屋拆成搶與不搶兩種選擇，並思考前一間與前兩間的最佳結果。程式、複雜度分析與 assertions 是我接著完成的。這次解法通過，但我還需要用另一題確認自己能在沒有提示時重新定義狀態。

題目

LeetCode 198：House Robber 給定一排房屋，每間房屋有一筆非負金額。不能在同一晚搶相鄰的兩間房屋，請計算最多能取得多少金額。

例如 [2, 7, 9, 3, 1] 的答案是 12，可以選擇金額 2、9、1。題目限制 1 <= nums.length <= 100 且 0 <= nums[i] <= 400。

直接搜尋的做法

最直接的想法，是在每間房屋分成兩條路：跳過目前房屋，或搶目前房屋並跳到下下間。

function robBruteForce(nums: number[], index = 0): number {
    if (index >= nums.length) return 0;

    const skip = robBruteForce(nums, index + 1);
    const take = nums[index] + robBruteForce(nums, index + 2);

    return Math.max(skip, take);
}

這段程式直接反映題意，但不同分支會重複計算相同索引之後的答案。時間上界是 O(2ⁿ)，遞迴呼叫堆疊為 O(n)。輸入上限雖然只有 100，這種成長速度仍然不可用。

我的解法

我使用三個變數保存前面的結果：

function rob(nums: number[]): number {
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    let p1 = nums[0];
    let p2 = nums[1];
    let max = Math.max(p1, p2);

    for (let i = 2; i < nums.length; i++) {
        const curr = Math.max(nums[i] + p1, p2);
        p1 = Math.max(p1, p2);
        p2 = curr;
        max = Math.max(curr, max);
    }

    return max;
}

這份程式在題目限制內會得到正確答案。第一次處理 i = 2 時，p1 是第一間的金額，p2 是第二間的金額。curr 比較「第三間加第一間」與「只選第二間」。因為金額不會是負數，第三間加第一間不會比第一間更差，因此沒有漏掉只選第一間的情況。

第一輪結束後，p1 = Math.max(p1, p2) 開始保存處理到前一個位置的最佳答案，p2 則保存目前最佳答案。後續迴圈因此符合標準動態規劃關係。

問題不在輸出，而在狀態很難一句話講清楚：p2 一開始只是第二間的金額，第一輪後才變成截至目前的最佳答案；max 又重複保存歷史最佳值。這使正確性依賴非負限制，也增加了證明與維護成本。

狀態更清楚的版本

我後來整理出一個等價但更直接的寫法。兩個變數從頭到尾維持相同意義，不需要按陣列長度分支，也不需要額外的 max。

function rob(nums: number[]): number {
    let twoBack = 0;
    let oneBack = 0;

    for (const amount of nums) {
        const current = Math.max(oneBack, twoBack + amount);
        twoBack = oneBack;
        oneBack = current;
    }

    return oneBack;
}

處理目前房屋前：

• oneBack 是處理完前一間房屋後的最大金額。
• twoBack 是處理完前兩間房屋後的最大金額。

如果不搶目前房屋，答案維持 oneBack。如果搶目前房屋，就不能搶前一間，所以金額是 twoBack + amount。比較兩者後得到 current，再把狀態往前移一格。

跟著 [2, 7, 9, 3, 1] 走一次

看到金額 3 時，搶它只能得到 7 + 3 = 10，不搶則能保留 11，所以最佳值不變。最後看到金額 1，選擇 11 + 1 得到 12。

正確性不變量

每次開始處理一間房屋時，oneBack 保存所有已處理到前一間房屋的合法方案中最大金額，twoBack 保存處理到前兩間房屋的最大金額。

任何最佳方案只會落在兩種情況之一：沒有選目前房屋，值為 oneBack；或選了目前房屋，因此不能選前一間，值為 twoBack + amount。兩種情況互斥且涵蓋所有合法方案，取較大值就是目前前綴的最佳答案。

更新後，twoBack 接手舊的 oneBack，oneBack 接手 current，所以不變量可延續到下一輪。走完整個陣列後，oneBack 就是所有房屋的最佳答案。

複雜度

兩個線性版本都只走訪陣列一次，時間複雜度是 O(n)。它們沒有建立與輸入長度一起成長的資料結構，額外空間是 O(1)。

可執行測試

我原本提供四個 assertions。再補上官方第二個範例、全零與容易檢查狀態更新的案例：

import assert from "node:assert/strict";

assert.equal(rob([2, 1, 1, 2]), 4);
assert.equal(rob([1, 3, 3, 1]), 4);
assert.equal(rob([0]), 0);
assert.equal(rob([1, 2, 3, 1]), 4);
assert.equal(rob([2, 7, 9, 3, 1]), 12);
assert.equal(rob([5, 1, 1, 5]), 10);
assert.equal(rob([0, 0, 0, 0]), 0);

這七組案例已實際執行通過。測試能檢查初始值與更新順序，但正確性仍要靠狀態定義與不變量說明。

常見錯誤

• 把題目理解成只比較奇數與偶數索引。最佳選擇不一定固定落在其中一組。
• 搶目前房屋時加上前一間的最佳值，可能把相鄰房屋一起算進去。
• 更新狀態的順序錯誤，導致 current 使用到本輪的新值。
• 只保存目前最大金額，卻說不清楚它涵蓋到哪個索引。
• 寫出遞迴關係後，沒有移除重複子問題。

這次學到的事

動態規劃的變數名稱不只是可讀性問題。若我無法固定說出每個變數在迴圈開始時代表什麼，正確性通常也很難證明。

我原本的程式在官方限制內成立，但要繞一圈才能解釋 p2 的意義為什麼在第一輪後改變。把狀態固定為「前一個前綴的最佳答案」與「前兩個前綴的最佳答案」後，程式更短，選擇也直接對應題意。下一次複習的重點，是不看文章寫出這個不變量，而不是只記住兩行更新公式。

參考資料

• LeetCode 198：House Robber：正式題意、範例與限制。
• Node.js assert：本文 assertions 使用的標準模組。