動態規劃就是把一個大問題一步步降解成越來越小的子問題，直到子問題小到可以用確定的條件來解答，即按照順序，從基元問題一步步擴大問題的規模，直到問題的規模覆蓋了我要求解的問題。每一個規模的問題的解叫做一個狀態，每個不同規模的問題的解的關係叫做狀態轉移方程，實際應用中無非就是利用歷史記錄，來避免我們的重複計算。而這些歷史記錄，我們得需要一些變量來保存，一般是用一維數組或者二維數組來保存，綜上所述的動態規劃問題其實可以簡化成為三個步驟，用於解決大部分的動態規劃問題。
本期例題：LeetCode 198. House Robber 打家劫舍（Easy）
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例：
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然後偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
定義子問題
寫出子問題的遞推關係
確定 DP 數組的計算順序
步驟一：定義子問題
子問題是和原問題相似，但規模較小的問題。例如這道打家劫舍問題，原問題是「從全部房子中能偷到的最大金額」，將問題的規模縮小，子問題就是「從 k個房子中能偷到的最大金額」，用 f(k)表示。
圖1 打家劫舍問題的子問題定義
可以看到，子問題是參數化的，我們定義的子問題中有參數k 。假設一共有 n個房子的話，就一共有 n個子問題。動態規劃實際上就是通過求這一堆子問題的解，來求出原問題的解。這要求子問題需要具備兩個性質：
這一步是求解動態規劃問題最關鍵的一步。然而，這一步也是最無法在代碼中體現出來的一步,我們來分析一下這道題的遞推關係：
假設一共有 n個房子，每個房子的金額分別是
k個房子中最後一個房子是Hk-1 。如果不偷這個房子，那麼問題就變成在前 k-1個房子中偷到最大的金額，也就是子問題 f(k-1)。如果偷這個房子，那麼前一個房子 Hk-2顯然不能偷，其他房子不受影響。那麼問題就變成在前 k-1個房子中偷到的最大的金額。兩種情況中，選擇金額較大的一種結果。
另外，我們在寫遞推關係的時候，還要注意遞推關係的 base case。這樣才能構成完整的遞推關係，後面寫代碼也不容易在邊界條件上出錯。在這道題中，是k=0 和 k=1時的子問題：
在確定了子問題的遞推關係之後，下一步就是依次計算出這些子問題了。
DP 數組也可以叫「子問題數組」，因為 DP 數組中的每一個元素都對應一個子問題。如下圖所示，dp[k] 對應子問題 f(k)，即偷前 k 間房子的最大金額。
圖3 DP 數組與子問題的對應關係
那麼，只要搞清楚了子問題的計算順序，就可以確定 DP 數組的計算順序。對於打家劫舍問題，我們分析子問題的依賴關係，發現每個 f(k)依賴f(k-1) 和 f(k-2)。也就是說，dp[k] 依賴 dp[k-1] 和 dp[k-2]，如下圖所示。
圖4 DP 數組的依賴順序
那麼，既然 DP 數組中的依賴關係都是向右指的，DP 數組的計算順序就是從左向右。這樣我們可以保證，計算一個子問題的時候，它所依賴的那些子問題已經計算出來了。
確定了 DP 數組的計算順序之後，我們就可以寫出題解代碼了：
public int rob(int[] nums) { if (nums.length == 0) { return 0; }
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]; } 本文用打家劫舍問題展示了動態規劃問題的基本解題三步驟。動態規劃問題種類繁多，有些題目非常有難度，但這些問題千變萬化也離不開這三個基本解題步驟，只不過是把三步驟的某些步驟變得更難了。例如：
在「定義子問題」的步驟，有的題目需要定義二維、三維的子問題。
在「子問題遞推關係」的步驟，有的題目需要分情況討論，有複雜的 max、min、sum 表達式。
在「DP 數組計算順序」的步驟，有的題目需要反向計算，甚至斜向計算。