LeetCode 例題精講 | 14 打家劫舍問題:動態規劃的解題四步驟

本期例題：LeetCode 198. House Robber 打家劫舍（Easy）

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

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

示例：

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

House Robber 問題（翻譯為小偷問題、打家劫舍問題）是一道非常經典的動態規劃入門題目。如果你對於動態規劃還不是很了解，或者沒怎麼做過動態規劃的題目的話，那麼我非常建議你用 House Robber 這道題來入門。

動態規劃可能被很多同學奉為最難理解的算法題類型，因為它的解法很靈活，變化很多。但是動態規劃又經常作為筆試題的壓軸，我們不得不去面對它。

其實，動態規劃是一類很講究「觸類旁通」的題型。很多動態規劃的解法需要你做過某一類型的例題，再做類似的題目的時候就可以想起來相應的思路。如果你做過不少題目，但是拿到新的題目依然沒有思路，那說明你做過的題目不夠典型。例如很多文章拿來大講特講的換硬幣問題，實際上並不太適合用來理解動態規劃的思想。

這正是我寫《LeetCode 例題精講》系列文章的意義所在。我的文章會做到兩點，一是選擇最有代表性的例題，二是通過該例題講解一類問題的解題套路。從本期開始的幾篇文章我會講解動態規劃問題，每篇文章用一道最典型的例題，帶你學習動態規劃的解題套路。

本文選擇一個非常典型的動態規劃問題：打家劫舍，在一步步求解這道題的過程中，講解動態規劃題目的四個基本步驟。

動態規劃的解題四步驟

動態規劃的的四個解題步驟是：

不瞞你說，在 LeetCode 上我做過的幾十道動態規劃題目，都是用這個解題四步驟做出來的。這個解題步驟適用於任何一道動態規劃題目，能夠讓你很快理清解題的各個要點。

步驟一：定義子問題

稍微接觸過一點動態規劃的朋友都知道動態規劃有一個「子問題」的定義。什麼是子問題？子問題是和原問題相似，但規模較小的問題。例如這道打家劫舍問題，原問題是「從全部房子中能偷到的最大金額」，將問題的規模縮小，子問題就是「從

打家劫舍問題的子問題定義

可以看到，子問題是參數化的，我們定義的子問題中有參數

原問題要能由子問題表示。例如這道題中，一個子問題的解要能通過其他子問題的解求出。例如這道題中，

打家劫舍問題由於比較簡單，定義子問題實際上是很直觀的。一些比較難的動態規劃題目可能需要一些定義子問題的技巧。

步驟二：寫出子問題的遞推關係

這一步是求解動態規劃問題最關鍵的一步。然而，這一步也是最無法在代碼中體現出來的一步。在做題的時候，最好把這一步的思路用注釋的形式寫下來。做動態規劃題目不要求快，而要確保無誤。否則，寫代碼五分鐘，找 bug 半小時，豈不美哉？

我們來分析一下這道題的遞推關係：

假設一共有

子問題的遞推關係

另外，我們在寫遞推關係的時候，還要注意遞推關係的 base case。這樣才能構成完整的遞推關係，後面寫代碼也不容易在邊界條件上出錯。在這道題中，是

步驟三：確定 DP 數組的計算順序

在確定了子問題的遞推關係之後，下一步就是依次計算出這些子問題了。在很多教程中都會寫，動態規劃有兩種計算順序，一種是自頂向下的、使用備忘錄的遞歸方法，一種是自底向上的、使用 DP 數組的循環方法。不過在普通的動態規劃題目中，99% 的情況我們用循環方法就很好解決，所以我們最好在一開始就堅持自底向上方法，使用 DP 數組，這樣才有助於領悟動態規劃的真正精髓。

DP 數組也可以叫「子問題數組」，因為 DP 數組中的每一個元素都對應一個子問題。如下圖所示，dp[k] 對應子問題

DP 數組與子問題的對應關係

那麼，只要搞清楚了子問題的計算順序，就可以確定 DP 數組的計算順序。對於打家劫舍問題，我們分析子問題的依賴關係，發現每個

DP 數組的依賴順序

那麼，既然 DP 數組中的依賴關係都是向右指的，DP 數組的計算順序就是從左向右。這樣我們可以保證，計算一個子問題的時候，它所依賴的那些子問題已經計算出來了。

確定了 DP 數組的計算順序之後，我們就可以寫出題解代碼了：

public int rob(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    // 子問題：
    // f(k) = 偷 [0..k) 房間中的最大金額

    // f(0) = 0
    // f(1) = nums[0]
    // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int k = 2; k <= N; k++) {
        // 套用子問題的遞推關係
        dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
    }
    return dp[N];
}
注意在上面的代碼中，有一大段關於子問題定義、遞推關係的公式。在面試的時候，我們一般需要先把子問題的定義、遞推關係給面試官解釋清楚，同時順手把這些內容用注釋的形式寫下來。這樣一來讓自己寫代碼不容易出錯，二來也能讓面試官更好地理解自己的思路。
步驟四：空間優化
空間優化是動態規劃問題的進階內容了。對於初學者來說，可以不掌握這部分內容，寫出來的代碼無非是空間複雜度高一些。不過，打家劫舍問題同樣是空間優化的一個很好的例子，所以你不妨了解一下。
讓我們回顧一下在編程入門階段學習的斐波那契數列的求解方法。斐波那契數列的遞推關係是 
// 計算斐波那契數列
// f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2)
int fib(int n) {
    if (n <= 2) {
        return 1;
    }
    int a = 1;
    int b = 1;
    for (int i = 2; i < n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}
請記住這段代碼，這段我們很早就會的代碼裡，其實蘊含了打家劫舍類動態規劃問題的空間優化技巧。
空間優化的基本原理是，很多時候我們並不需要始終持有全部的 DP 數組。對於打家劫舍問題，我們發現，最後一步計算 
那麼，我們可以只用兩個變量保存兩個子問題的結果，就可以依次計算出所有的子問題。這樣一來，空間複雜度也從 
空間優化前後對比（動圖）
優化後的代碼如下所示：
public int rob(int[] nums) {
    int prev = 0;
    int curr = 0;

    // 每次循環，計算「偷到當前房子為止的最大金額」
    for (int i : nums) {
        // 循環開始時，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        // dp[k] = max{ dp[k-1], dp[k-2] + i }
        int temp = Math.max(curr, prev + i);
        prev = curr;
        curr = temp;
        // 循環結束時，curr 表示 dp[k]，prev 表示 dp[k-1]
    }

    return curr;
}
可以看到，我們只用到了三個變量：prev、curr 和 temp。在每一輪循環中，prev 都表示 dp[k-2]，curr 都表示 dp[k-1]，而 temp 負責計算出 dp[k] 的值，再往前循環複製。這三個變量的操作方式，和斐波那契數列中的三個變量一模一樣。
如果你是 Python 選手的話，還可以利用多重賦值的語法，去掉 temp 變量，在循環裡只用一行代碼：
def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0
    
    # 每次循環，計算「偷到當前房子為止的最大金額」
    for i in nums:
        # 循環開始時，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # 循環結束時，curr 表示 dp[k]，prev 表示 dp[k-1]

    return curr
總結 
本文用打家劫舍問題展示了動態規劃問題的基本解題四步驟。動態規劃問題種類繁多，有些題目非常有難度，但這些問題千變萬化也離不開這四個基本解題步驟，只不過是把四步驟的某些步驟變得更難了。例如：
在「定義子問題」的步驟，有的題目需要定義二維、三維的子問題。在「子問題遞推關係」的步驟，有的題目需要分情況討論，有複雜的 max、min、sum 表達式。在「DP 數組計算順序」的步驟，有的題目需要反向計算，甚至斜向計算。在「空間優化」的步驟，有的題目需要使用臨時變量，使用特殊的計算順序。
那麼你可能要問，題目千變萬化，怎麼才能全部學會呢？答案是由易到難、循序漸進，吃透例題，觸類旁通。
看到這裡，恭喜你走好了動態規劃入門的第一步。接下來，我會循序漸進地講解其他動態規劃題目，讓你能逐步掌握動態規劃問題的技巧，敬請期待。
往期文章
我是 nettee，致力於分享面試算法的解題套路，讓你真正掌握解題技巧，做到舉一反三。我的《LeetCode 例題精講》系列文章正在寫作中，關注我的公眾號，獲取最新文章。