動态規劃之初識動規：有了四步解題法模闆，再也不害怕動态規劃！

導言

動态規劃問題一直是算法面試當中的重點和難點，并且動态規劃這種通過空間換取時間的算法思想在實際的工作中也會被頻繁用到，這篇文章的目的主要是解釋清楚 什麼是動态規劃，還有就是面對一道動态規劃問題，一般的 思考步驟

什麼是動态規劃

如果你還沒有聽說過動态規劃，或者僅僅隻有耳聞，或許你可以看看 Quora 上面的這個 回答。

用一句話解釋動态規劃就是 “記住你之前做過的事”，如果更準确些，其實是 “記住你之前得到的答案”。

我舉個大家工作中經常遇到的例子。

在軟體開發中，大家經常會遇到一些系統配置的問題，配置不對，系統就會報錯，這個時候一般都會去 Google 或者是查閱相關的文檔，花了一定的時間将配置修改好。

過了一段時間，去到另一個系統，遇到類似的問題，這個時候已經記不清之前修改過的配置檔案長什麼樣，這個時候有兩種方案，一種方案還是去 Google 或者查閱文檔，另一種方案是借鑒之前修改過的配置，第一種做法其實是萬金油，因為你遇到的任何問題其實都可以去 Google，去查閱相關檔案找答案，但是這會花費一定的時間，相比之下，第二種方案肯定會更加地節約時間，但是這個方案是有條件的，條件如下：

• 之前的問題和目前的問題有着關聯性，換句話說，之前問題得到的答案可以幫助解決目前問題
• 需要記錄之前問題的答案

當然在這個例子中，可以看到的是，上面這兩個條件均滿足，大可去到之前配置過的檔案中，将配置拷貝過來，然後做些細微的調整即可解決目前問題，節約了大量的時間。

不知道你是否從這些描述中發現，對于一個動态規劃問題，我們隻需要從兩個方面考慮，那就是 找出問題之間的聯系，以及 記錄答案，這裡的難點其實是找出問題之間的聯系，記錄答案隻是順帶的事情，利用一些簡單的資料結構就可以做到。

概念

上面的解釋如果大家可以了解的話，接

動态規劃算法是通過拆分問題，定義問題狀态和狀态之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。它的幾個重要概念如下所述。

階段：對于一個完整的問題過程，适當的切分為若幹個互相聯系的子問題，每次在求解一個子問題，則對應一個階段，整個問題的求解轉化為按照階段次序去求解。

狀态：狀态表示每個階段開始時所處的客觀條件，即在求解子問題時的已知條件。狀态描述了研究的問題過程中的狀況。

決策：決策表示當求解過程處于某一階段的某一狀态時，可以根據目前條件作出不同的選擇，進而确定下一個階段的狀态，這種選擇稱為決策。

政策：由所有階段的決策組成的決策序列稱為全過程政策，簡稱政策。

最優政策：在所有的政策中，找到代價最小，性能最優的政策，此政策稱為最優政策。

狀态轉移方程：狀态轉移方程是确定兩個相鄰階段狀态的演變過程，描述了狀态之間是如何演變的。

思考動态規劃問題的四個步驟

一般解決動态規劃問題，分為四個步驟，分别是

• 問題拆解，找到問題之間的具體聯系
• 狀态定義
• 遞推方程推導
• 實作

這裡面的重點其實是前兩個，如果前兩個步驟順利完成，後面的遞推方程推導和代碼實作會變得非常簡單。

這裡還是拿 Quora 上面的例子來講解，“1+1+1+1+1+1+1+1” 得出答案是 8，那麼如何快速計算 “1+ 1+1+1+1+1+1+1+1”，我們首先可以對這個大的問題進行拆解，這裡我說的大問題是 9 個 1 相加，這個問題可以拆解成 1 + “8 個 1 相加的答案”，8 個 1 相加繼續拆，可以拆解成 1 + “7 個 1 相加的答案”，... 1 + “0 個 1 相加的答案”，到這裡，第一個步驟

狀态定義 其實是需要思考在解決一個問題的時候我們做了什麼事情，然後得出了什麼樣的答案，對于這個問題，目前問題的答案就是目前的狀态，基于上面的問題拆解，你可以發現兩個相鄰的問題的聯系其實是 ​

​後一個問題的答案 = 前一個問題的答案 + 1​

​，這裡，狀态的每次變化就是 +1。

定義好了狀态，遞推方程就變得非常簡單，就是 ​

​dp[i] = dp[i - 1] + 1​

​​，這裡的 ​

​dp[i]​

​​ 記錄的是目前問題的答案，也就是目前的狀态，​

​dp[i - 1]​

​ 記錄的是之前相鄰的問題的答案，也就是之前的狀态，它們之間通過 +1 來實作狀态的變更。

最後一步就是實作了，有了狀态表示和遞推方程，實作這一步上需要重點考慮的其實是初始化，就是用什麼樣的資料結構，根據問題的要求需要做那些初始值的設定。

public int dpExample(int n) {
    int[] dp = new int[n + 1];  // 多開一位用來存放 0 個 1 相加的結果

    dp[0] = 0;      // 0 個 1 相加等于 0

    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
    }

    return dp[n];
}      

你可以看到，動态規劃這四個步驟其實是互相遞進的，狀态的定義離不開問題的拆解，遞推方程的推導離不開狀态的定義，最後的實作代碼的核心其實就是遞推方程，這中間如果有一個步驟卡殼了則會導緻問題無法解決，當問題的複雜程度增加的時候，這裡面的思維複雜程度會上升。

接下來我們再來看看 LeetCode 上面的幾道題目，通過題目再來走一下這些個分析步驟。

題目實戰

爬樓梯

但凡涉及到動态規劃的題目都離不開一道例題：爬樓梯（LeetCode 第 70 号問題）。

題目描述

假設你正在爬樓梯。需要 n

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階      

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階      

題目解析

爬樓梯，可以爬一步也可以爬兩步，問有多少種不同的方式到達終點，我們按照上面提到的四個步驟進行分析：

• 問題拆解：

我們到達第 n 個樓梯可以從第 n - 1 個樓梯和第 n - 2 個樓梯到達，是以第 n 個問題可以拆解成第 n - 1 個問題和第 n - 2 個問題，第 n - 1 個問題和第 n - 2 個問題又可以繼續往下拆，直到第 0 個問題，也就是第 0 個樓梯 (起點)

• 狀态定義

“問題拆解” 中已經提到了，第 n 個樓梯會和第 n - 1 和第 n - 2 個樓梯有關聯，那麼具體的聯系是什麼呢？你可以這樣思考，第 n - 1 個問題裡面的答案其實是從起點到達第 n - 1 個樓梯的路徑總數，n - 2 同理，從第 n - 1 個樓梯可以到達第 n 個樓梯，從第 n - 2 也可以，并且路徑沒有重複，是以我們可以把第 i 個狀态定義為 “從起點到達第 i 個樓梯的路徑總數”，狀态之間的聯系其實是相加的關系。

• 遞推方程

“狀态定義” 中我們已經定義好了狀态，也知道第 i 個狀态可以由第 i - 1 個狀态和第 i - 2 個狀态通過相加得到，是以遞推方程就出來了 ​

​dp[i] = dp[i - 1] + dp[i - 2]​

​

• 實作

你其實可以從遞推方程看到，我們需要有一個初始值來友善我們計算，起始位置不需要移動 ​

​dp[0] = 0​

​​，第 1 層樓梯隻能從起始位置到達，是以 ​

​dp[1] = 1​

​​，第 2 層樓梯可以從起始位置和第 1 層樓梯到達，是以 ​

​dp[2] = 2​

​，有了這些初始值，後面就可以通過這幾個初始值進行遞推得到。

參考代碼

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }

    int[] dp = new int[n + 1];  // 多開一位，考慮起始位置

    dp[0] = 0; dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}      

三角形最小路徑和

LeetCode 第 120 号問題：三角形最小路徑和。

題目描述

給定一個三角形，找出自頂向下的最小路徑和。每一步隻能移動到下一行中相鄰的結點上。

例如，給定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]      

自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

說明：

如果你可以隻使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題，那麼你的算法會很加分。

題目解析

給定一個三角形數組，需要求出從上到下的最小路徑和，也和之前一樣，按照四個步驟來分析：

• 問題拆解：

這裡的總問題是求出最小的路徑和，路徑是這裡的分析重點，路徑是由一個個元素組成的，和之前爬樓梯那道題目類似，​

​[i][j]​

​​ 位置的元素，經過這個元素的路徑肯定也會經過 ​

​[i - 1][j]​

​​ 或者 ​

​[i - 1][j - 1]​

​，是以經過一個元素的路徑和可以通過這個元素上面的一個或者兩個元素的路徑和得到。

• 狀态定義

狀态的定義一般會和問題需要求解的答案聯系在一起，這裡其實有兩種方式，一種是考慮路徑從上到下，另外一種是考慮路徑從下到上，因為元素的值是不變的，是以路徑的方向不同也不會影響最後求得的路徑和，如果是從上到下，你會發現，在考慮下面元素的時候，起始元素的路徑隻會從​

​[i - 1][j]​

​​ 獲得，每行當中的最後一個元素的路徑隻會從 ​

​[i - 1][j - 1]​

​ 獲得，中間二者都可，這樣不太好實作，是以這裡考慮從下到上的方式，狀态的定義就變成了 “最後一行元素到目前元素的最小路徑和”，對于 ​

​[0][0]​

​ 這個元素來說，最後狀态表示的就是我們的最終答案。

• 遞推方程

“狀态定義” 中我們已經定義好了狀态，遞推方程就出來了

​

​dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]​

​

• 實作

這裡初始化時，我們需要将最後一行的元素填入狀态數組中，然後就是按照前面分析的政策，從下到上計算即可

參考代碼

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();

    int[][] dp = new int[n][n];

    List<Integer> lastRow = triangle.get(n - 1);

    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = lastRow.get(i);
    }

    for (int i = n - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }

    return dp[0][0];
}      

最大子序和

LeetCode 第 53 号問題：最大子序和。

題目描述

給定一個整數數組 nums

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。      

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

題目解析

求最大子數組和，非常經典的一道題目，這道題目有很多種不同的做法，而且很多算法思想都可以在這道題目上面展現出來，比如動态規劃、貪心、分治，還有一些技巧性的東西，比如字首和數組，這裡還是使用動态規劃的思想來解題，套路還是之前的四步驟：

• 問題拆解：

問題的核心是子數組，子數組可以看作是一段區間，是以可以由起始點和終止點确定一個子數組，兩個點中，我們先确定一個點，然後去找另一個點，比如說，如果我們确定一個子數組的截止元素在 i 這個位置，這個時候我們需要思考的問題是 “以 i 結尾的所有子數組中，和最大的是多少？”，然後我們去試着拆解，這裡其實隻有兩種情況：

• i 這個位置的元素自成一個子數組
• i 位置的元素的值 +以 i - 1 結尾的所有子數組中的子數組和最大的值

你可以看到，我們把第 i 個問題拆成了第 i - 1 個問題，之間的聯系也變得清晰

• 狀态定義

通過上面的分析，其實狀态已經有了，​

​dp[i]​

​ 就是 “以 i 結尾的所有子數組的最大值”

• 遞推方程

拆解問題的時候也提到了，有兩種情況，即目前元素自成一個子數組，另外可以考慮前一個狀态的答案，于是就有了

​

​dp[i] = Math.max(dp[i - 1] + array[i], array[i])​

​

化簡一下就成了：

​

​dp[i] = Math.max(dp[i - 1], 0) + array[i]​

​

• 實作

題目要求子數組不能為空，是以一開始需要初始化，也就是 ​

​dp[0] = array[0]​

​，保證最後答案的可靠性，另外我們需要用一個變量記錄最後的答案，因為子數組有可能以數組中任意一個元素結尾

參考代碼

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;

    int[] dp = new int[n];

    dp[0] = nums[0];

    int result = dp[0];

    for (int i = 1; i < n; ++i) {
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        result = Math.max(result, dp[i]);
    }

    return result;
}      

總結

通過這幾個簡單的例子，相信你不難發現，解動态規劃題目其實就是拆解問題，定義狀态的過程，嚴格說來，動态規劃并不是一個具體的算法，而是淩駕于算法之上的一種 思想

這種思想強調的是從局部最優解通過一定的政策推得全局最優解，從子問題的答案一步步推出整個問題的答案，并且利用空間換取時間。從很多算法之中你都可以看到動态規劃的影子，是以，還是那句話 技術都是相通的，找到背後的本質思想是關鍵。

我的網站：

​​有了四步解題法模闆，再也不害怕動态規劃！-五分鐘學算法​​

我的專欄：

​​和程式員小吳一起學算法​​

❤️ 看完三件事：

如果你覺得這篇内容對你挺有啟發，我想邀請你幫我三個忙：

1. 點贊，讓更多的人也能看到這篇内容（收藏不點贊，都是耍流氓 -_-）
2. 關注我和專欄，讓我們成為長期關系
3. 關注公衆号「五分鐘學算法」，第一時間閱讀最新的算法文章，公衆号背景回複 1024 送你 50 本 算法程式設計書籍。