面向大象程式設計
本期例題：LeetCode 198. House Robber 打家劫舍（Easy）
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例：
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
House Robber 問題（翻譯為小偷問題、打家劫舍問題）是一道非常經典的動态規劃入門題目。如果你對于動态規劃還不是很了解，或者沒怎麼做過動态規劃的題目的話，那麼我非常建議你用 House Robber 這道題來入門。
動态規劃可能被很多同學奉為最難了解的算法題類型，因為它的解法很靈活，變化很多。但是動态規劃又經常作為筆試題的壓軸，我們不得不去面對它。
其實，動态規劃是一類很講究「觸類旁通」的題型。很多動态規劃的解法需要你做過某一類型的例題，再做類似的題目的時候就可以想起來相應的思路。如果你做過不少題目，但是拿到新的題目依然沒有思路，那說明你做過的題目不夠典型。例如很多文章拿來大講特講的換硬币問題，實際上并不太适合用來了解動态規劃的思想。
這正是我寫《LeetCode 例題精講》系列文章的意義所在。我的文章會做到兩點，一是選擇最有代表性的例題，二是通過該例題講解一類問題的解題套路。從本期開始的幾篇文章我會講解動态規劃問題，每篇文章用一道最典型的例題，帶你學習動态規劃的解題套路。
本文選擇一個非常典型的動态規劃問題：打家劫舍，在一步步求解這道題的過程中，講解動态規劃題目的四個基本步驟。
動态規劃的解題四步驟
動态規劃的的四個解題步驟是：
- 定義子問題
- 寫出子問題的遞推關系
- 确定 DP 數組的計算順序
- 空間優化（可選）
不瞞你說，在 LeetCode 上我做過的幾十道動态規劃題目，都是用這個解題四步驟做出來的。這個解題步驟适用于任何一道動态規劃題目，能夠讓你很快理清解題的各個要點。
步驟一：定義子問題
稍微接觸過一點動态規劃的朋友都知道動态規劃有一個「子問題」的定義。什麼是子問題？子問題是和原問題相似，但規模較小的問題。例如這道打家劫舍問題，原問題是「從全部房子中能偷到的最大金額」，将問題的規模縮小，子問題就是「從
個房子中能偷到的最大金額」，用
打家劫舍問題的子問題定義
可以看到，子問題是參數化的，我們定義的子問題中有參數
。假設一共有
個房子的話，就一共有
- 原問題要能由子問題表示。例如這道題中，
-
一個子問題的解要能通過其他子問題的解求出。例如這道題中，
可以由
和
打家劫舍問題由于比較簡單，定義子問題實際上是很直覺的。一些比較難的動态規劃題目可能需要一些定義子問題的技巧。
步驟二：寫出子問題的遞推關系
這一步是求解動态規劃問題最關鍵的一步。然而，這一步也是最無法在代碼中展現出來的一步。在做題的時候，最好把這一步的思路用注釋的形式寫下來。做動态規劃題目不要求快，而要確定無誤。否則，寫代碼五分鐘，找 bug 半小時，豈不美哉？
我們來分析一下這道題的遞推關系：
假設一共有
個房子，每個房子的金額分别是
，子問題
表示偷前
個房子（即
）中能偷到的最大金額。那麼，偷
子問題的遞推關系
個房子中最後一個房子是
。如果不偷這個房子，那麼問題就變成在前
個房子中偷到最大的金額，也就是子問題
。如果偷這個房子，那麼前一個房子
顯然不能偷，其他房子不受影響。那麼問題就變成在前
另外，我們在寫遞推關系的時候，還要注意遞推關系的 base case。這樣才能構成完整的遞推關系，後面寫代碼也不容易在邊界條件上出錯。在這道題中，是
和
-
當
時，沒有房子，是以
。
-
當
時，隻有一個房子，偷這個房子即可，是以
。
步驟三：确定 DP 數組的計算順序
在确定了子問題的遞推關系之後，下一步就是依次計算出這些子問題了。在很多教程中都會寫，動态規劃有兩種計算順序，一種是自頂向下的、使用備忘錄的遞歸方法，一種是自底向上的、使用 DP 數組的循環方法。不過在普通的動态規劃題目中，99% 的情況我們用循環方法就很好解決，是以我們最好在一開始就堅持自底向上方法，使用 DP 數組，這樣才有助于領悟動态規劃的真正精髓。
DP 數組也可以叫「子問題數組」，因為 DP 數組中的每一個元素都對應一個子問題。如下圖所示，
dp[k]
對應子問題
，即偷前
DP 數組與子問題的對應關系
那麼，隻要搞清楚了子問題的計算順序，就可以确定 DP 數組的計算順序。對于打家劫舍問題，我們分析子問題的依賴關系，發現每個
依賴
和
。也就是說，
dp[k]
依賴
dp[k-1]
和
dp[k-2]
，如下圖所示。
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];
} 注意在上面的代碼中，有一大段關于子問題定義、遞推關系的公式。在面試的時候，我們一般需要先把子問題的定義、遞推關系給面試官解釋清楚，同時順手把這些内容用注釋的形式寫下來。這樣一來讓自己寫代碼不容易出錯，二來也能讓面試官更好地了解自己的思路。
步驟四：空間優化
空間優化是動态規劃問題的進階内容了。對于初學者來說，可以不掌握這部分内容，寫出來的代碼無非是空間複雜度高一些。不過，打家劫舍問題同樣是空間優化的一個很好的例子，是以你不妨了解一下。
讓我們回顧一下在程式設計入門階段學習的斐波那契數列的求解方法。斐波那契數列的遞推關系是
。這是不是和打家劫舍問題一模一樣？計算斐波那契數列的時候，我們隻需要用到三個變量，并不需要什麼 DP 數組：
// 計算斐波那契數列
// 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 數組計算順序」的步驟，有的題目需要反向計算，甚至斜向計算。
- 在「空間優化」的步驟，有的題目需要使用臨時變量，使用特殊的計算順序。
那麼你可能要問，題目千變萬化，怎麼才能全部學會呢？答案是由易到難、循序漸進，吃透例題，觸類旁通。
看到這裡，恭喜你走好了動态規劃入門的第一步。接下來，我會循序漸進地講解其他動态規劃題目，讓你能逐漸掌握動态規劃問題的技巧，敬請期待。
推薦閱讀
• 60 個相見恨晚的神器工具• 一線網際網路公司技術面試的流程以及注意事項• 自學程式設計的八大誤區！克服它！• 新手如何有效的刷算法題（LeetCode）• 10款VS Code插件神器，第7款超級實用！• 在拼多多上班，是一種什麼樣的體驗？我tm心态崩了呀！• 寫給小白，從零開始擁有一個酷炫上線的網站！
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下“在看”~