動態規劃可以說是很多準備算法面試者的夢魘，大家都非常怕面試官會出動態規劃的題目，如果遇到一些做過的題目還好，但要是遇到了根本就沒有做過的，就無從下手了。 本節課從動態規劃的基本屬性，題目分類，解題思想，以及算法復雜度等方面來詳解動態規劃。 #### 判斷動態規劃 Wikipedia 定義：它既是一種數學優化的方法，同時也是編程的方法。 1. 是數學優化的方法——最優子結構 動態規劃是數學優化的方法指，動態規劃要解決的都是問題的最優解。而一個問題的最優解是由它的各個子問題的最優解決定的。 由此引出動態規劃的第一個重要的屬性：最優子結構（Optimal Substructure)。 一般由最優子結構，推導出一個狀態轉移方程 f(n)，就能很快寫出問題的遞歸實現方法。 ?2. 是編程的方法——重疊子問題 動態規劃是編程的方法指，可以借助編程的技巧去保證每個重疊的子問題只會被求解一次。 引出了動態規劃的第二個重要的屬性：重疊子問題（Overlapping Sub-problems）。? ? 下面通過幾個小例題來判斷其方法是否符合動態規劃。 **舉例 1**：斐波那契數列問題。 解法：為了求出第 5 個斐波那契數，得先求出第 4 個和第 3 個數，但是在求第 4 個數的時候，又得重復計算一次第 3 個數，同樣，對于第 2 個數的計算也出現了重復。 因此，判斷一個問題能不能稱得上是動態規劃的問題，需要看它是否同時滿足這兩個重要的屬性：最優子結構（Optimal Substructure）和重疊子問題（Overlapping Sub-problems） **舉例 2**：給定如下的一個有向圖，求出從頂點 A 到 C 的最長的路徑。要求路徑中的點只能出現一次。 按照題目的要求，可以看到，從 A 通往 C 有兩條最長的路徑：A -> B -> C 和?A -> D -> C。 對于?A -> B -> C，A 到 B 的最長距離是：A -> D -> C -> B B 到 C 的最長距離是：B -> A -> D -> C 組合路徑：A -> D -> C -> B -> A -> D -> C ? 上述答案并不滿足題目的要求。該題并沒有一個最優子結構，不是動態規劃問題。 **舉例 3**：歸并排序和快速排序是否屬于動態規劃？ 解法： 將要排序的數組分成兩半，然后遞歸地進行處理，滿足最優子結構的屬性； 不斷地對待排序的數組進行對半分的時候，兩半邊的數據并不重疊，不會遇到重復的子數組，不滿足重疊子問題的屬性。 因此這兩種算法不是動態規劃的方法。 * [ ] 例題分析 LeetCode 第 300 題：給定一個無序的整數數組，找到其中最長子序列長度。 說明： * 可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。 * 你算法的時間復雜度應該為 O(n2） 。 注意：子序列和子數組不同，它并不要求元素是連續的。 示例 ``` 輸入：[ 10, 9, 2, 5, 3, 7, 101, 18 ] 輸出：4? ``` 即，最長的上升子序列是 [2, 3, 7, 101]，它的長度是 4。 * [ ] 解題思路 在給定的數組里，有很多的上升子序列，例如：[10, 101]，[9, 101]，[2, 5, 7, 101]，以及 [2, 3, 7, 101]，只需要找出其中一個最長的。 思路 1：暴力法 找出所有的子序列，然后從中返回一個最長的。 從一個數組中羅列出所有的非空子數組有： n×(n + 1)/2 種，即 O(n2)，那么羅列出所有的非空子序列有 2n?1?種。復雜度將是 O(2n)。 思路 2：縮小問題規模 1. 找最優子結構：輸入規模對半分? ? [10, 9, 2, 5] 最長的子序列應該是 [2, 5]，而 [3, 7, 101, 4] 最長的子序列是 [3, 7, 101]，由于 3 比 5 小，無法簡單地組合在一起。即該方法下，總問題的解無法直觀地通過子問題的最優解求得。 2. 找最優子結構：每次減一個 假設 f(n) 表示的是數組 nums[0，…，n?1] 中最長的子序列，那么 f(n?1) 就是數組 nums[0，…，n?2] 中最長的子序列，依此類推，f(1) 就是 nums[0] 的最長子序列。 假設已經解決了 f(1)，f(2)，… f(n?1) 的問題，考慮最后一個數 nums[n?1]，也必然考慮到倒數第二個數 nums[n?2]，所以 f(n) 指：如果包含了最后的數，那么最長的子序列應該是什么。 注意：最后這個數必須包含在子序列當中的。 如何通過 f(1)，f(2)，…f(n?1) 推導出 f(n) 呢？由于最后一個數是 4，我們只需要在前面的 f(1)，f(2)，…f(n?1) 當中，找出一個以小于 4 的數作為結尾的最長的子序列，然后把 4 添加到最后，那么 f(n) 就一定是以 4 作為結尾的最長的子序列了。 最長的子序列并不一定會包含 4，遍歷 f(1)，f(2)，…f(n?1) ，找出最長的。例如，以 101 結尾的最長的上升子序列是什么。 總結解決動態規劃問題的兩個難點。 （1）如何定義 f(n) 對于這道題而言，f(n) 是以 nums[n?1] 結尾的最長的上升子序列的長度 （2）如何通過 f(1)，f(2)，…f(n?1) 推導出 f(n)，即狀態轉移方程 本題中，nums[n?1] 和比它小的每一個值 nums[i] 進行比較，其中 1<=i<n，加 1 即可。因此狀態轉移方程就是：f(n)=max (1 <= i < n?1, nums[i?1] < nums[n?1]) { f(i) } + 1 ?以上證明了這個問題有一個最優的子結構。 3. 找重疊子問題 在分析最后一個數 4 的時候，以 3 結尾的最長的上升子序列長度就是 f(5)，因為 3 是第 5 個數。把問題規模縮小 2 個，當前的數變成 101 的時候，找比它小的數，又發現了 3，這個時候又會去重復計算一遍 f(5)，說明該題有重疊的子問題。 因此，可以運用動態規劃的方法來解決這個問題。 * [ ] 遞歸（Recursion） 用遞歸的方法求解狀態轉移方程式 f(n)=max (1 <= i < n?1, nums[i?1] < nums[n?1]) { f(i) } + 1。 * 對于每個 n，要從 0 開始遍歷 * 在 n 之前，找出比 nums[n?1] 小的數 * 遞歸地調用 f 函數，找出最大的，最后加上 1 * 當 i 等于 0 的時候，應該返回 0；當 i 等于 1 的時候應該返回 1。 代碼實現 下面就是遞歸的代碼實現。 ``` class?LISRecursion?{ ????//?定義一個靜態變量?max，用來保存最終的最長的上升子序列的長度 ????static?int?max; ????public?int?f(int[]?nums,?int?n)?{ ????????if?(n?<=?1)?{ ????????????return?n; ????????} ???? ????????int?result=0,?maxEndingHere=1; ???? ????????//?從頭遍歷數組，遞歸求出以每個點為結尾的子數組中最長上升序列的長度 ????????for?(int?i=1;?i?<?n;?i++)?{ ????????????result=f(nums,?i); ????????????if?(nums[i?1]?<?nums[n?1]?&&?result?+?1?>?maxEndingHere)?{ ????????????????maxEndingHere=result?+?1; ????????????} ????????} ????????//?判斷一下，如果那個數比目前最后一個數要小，那么就能構成一個新的上升子序列? ????????if?(max?<?maxEndingHere)?{ ????????????max=maxEndingHere; ????????} ????????//?返回以當前數結尾的上升子序列的最長長度 ????????return?maxEndingHere; ????} ????public?int?LIS(int[]?nums)?{ ????????max=1; ????????f(nums,?nums.length); ????????return?max;? ????} } ``` 其中，實現狀態轉移方程，即 f 函數。 * 最基本的情況，當數組的長度為 0 時，沒有上升子序列，當數組長度為 1 時，最長的上升子序列長度是 1。 * maxEndingHere 變量的含義就是包含當前最后一個元素的情況下，最長的上升子序列長度。 **時間復雜度** 用公式法解決該遞歸問題的時間復雜度，如下。 當 n=1 的時候，遞歸直接返回 1，執行時間為 O(1)，即 T(1)=O(1) 當 n=2 的時候，內部調用了一次遞歸求解 T(1)，所以 T(2)=T(1) 當 n=3 的時候，T(3)=T(1) + T(2) … 以此類推， T(n?1)=T(1) + T(2) + … + T(n?2) T(n)=T(1) + T(2) + … + T(n?1) 通過觀察，我們得到：T(n)=2×T(n?1)，這并不滿足 T(n)=a×T(n / b) + f(n) 的關系式。但是 T(n) 等于兩倍的 T(n?1)，表明，我們的計算是成指數增長的，每次的計算都是先前的兩倍。所以 O(n)=O(2n)。 * [ ] 記憶化（Memoization） 由于遞歸的解法需要耗費非常多的重復計算，而且很多計算都是重疊的，避免重疊計算的一種辦法就是記憶化。 記憶化，就是將已經計算出來的結果保存起來，那么下次遇到相同的輸入時，直接返回保存好的結果，能夠有效節省了大量的計算時間。 代碼實現 在之前遞歸實現的基礎上實現記憶化，代碼如下。 ``` class LISMemoization { ? ?static int max; ? ?// 定義哈希表 cache，用來保存計算結果 ? ?static HashMap<Integer, Integer> cache; ? ? ? ?// 調用遞歸函數的時候，判斷 cache 里是否已經保留了這個值。是，則返回；不是，繼續遞歸調用 ? ?public int f(int[] nums, int n) { ? ? ? ?if (cache.containsKey(n)) { ? ? ? ? ? ?return cache.get(n); ? ? ? ?} ? ? ? ?if (n <= 1) { ? ? ? ? ? ?return n; ? ? ? ?} ? ? ? ?int result=0, maxEndingHere=1;? ? ? ? ?for (int i=1; i < n; i++) { ? ? ? ? ? ?... ? ? ? ?} ? ? ? ? ? ?if (max < maxEndingHere) { ? ? ? ? ? ?max=maxEndingHere; ? ? ? ?} ? ? ? ? ? ?// 在返回當前結果前，保存到 cache ? ? ? ?cache.put(n, maxEndingHere); ? ? ? ?return maxEndingHere; ? ?} } ``` **時間復雜度** 分析遞歸+記憶化的時間復雜度，如下。 1. 函數 f 按序傳遞n，n?1，n?2 … 最后是 1，把結果緩存并返回； 2. 遞歸返回到輸入 n； 3. 緩存里已經保存了 n?1 個結果； 4. for 循環調用遞歸函數 n?1 次，從 cache 里直接返回結果。 上述過程的時間復雜度是 O(1)。即將問題的規模大小從 n 逐漸減小到 1 的時候，通過將各個結果保存起來，可以將 T(1)，T(2)，….T(n?1) 的復雜度降低到線性的復雜度。 現在，回到 T(n)，在 for 循環里，嘗試著從 T(1)，T(2)….T(n?1) 里取出最大值，因此?O(T(n))=O(T(1) + T(2) + … + T(n?1))=O(1 + 2 + …. + n?1)=O(n×(n?1)/2)=O(n2)。 最后加上構建緩存 cache 的時間，整體的時間復雜度就是?O(f(n))=O(n) + O(n^2)=O(n2)。 通過記憶化的操作，我們把時間復雜度從 O(2n) 降低到了 O(n2)。 這種將問題規模不斷減少的做法，被稱為自頂向下的方法。但是，由于有了遞歸的存在，程序運行時對堆棧的消耗以及處理是很慢的，在實際工作中并不推薦。更好的辦法是自底向上。 * [ ] 自底向上（Bottom-Up） 自底向上指，通過狀態轉移方程，從最小的問題規模入手，不斷地增加問題規模，直到所要求的問題規模為止。依然使用記憶化避免重復的計算，不需要遞歸 建議：在面試的時候，如果能最終給出一個自底向上的方案和代碼，則比較完美。 ``` class?LISDP?{ ????public?int?LIS(int[]?nums,?int?n)?{ ????????int[]?dp=new?int[n];?//?一維數組?dp?存儲計算結果 ????????int?i,?j,?max=0; ???? ????????//?初始化?dp?數組里的每個元素的值為?1，即以每個元素作為結尾的最長子序列的長度初始化為?1 ????????for?(i=0;?i?<?n;?i++)?dp[i]=1; ????????//?自底向上地求解每個子問題的最優解 ????????for?(i=0;?i?<?n;?i++)?{ ????????????//?遍歷中遇到的每個元素?nums[j]?與?nums[i]?比較，若?nums[j]?<?nums[i]，說明?nums[i]?有機會構成上升序列，若新的上升序列比之前計算過的還要長，更新一下，保存到?cache?數組 ????????????for?(j=0;?j?<?i;?j++)?{ ????????????????if?(nums[j]?<?nums[i]?&&?dp[i]?<?dp[j]?+?1)?{ ????????????????????dp[i]=dp[j]?+?1; ????????????????} ????????????} ????????????//?用當前計算好的長度與全局的最大值進行比較?? ????????????max=Math.max(max,?dp[i]); ????????} ????????//?最后得出最長的上升序列的長度 ????????return?max;?? ???? ????} ???? } ``` **時間復雜度** 由上可知，這一個雙重循環。當 i=0 的時候，內循環執行 ?0 次；當 i=1 的時候，內循環執行 1 次……以此類推，當 i=n?1 的時候，內循環執行了 n?1 次，因此，總體的時間復雜度是?O(1 + 2 + .. + n?1)=O(n×(n?1) / 2)=O(n2)。 **動態規劃面試題分類** 運用動態規劃去解決問題，最難的地方有兩個： 1. 應當采用什么樣的數據結構來保存什么樣的計算結果 2. 如何利用保存下來的計算結果推導出狀態轉移方程 第一個難點，不僅是為了避免重復的計算，也是推導狀態轉移方程的關鍵。這一難點往往是在把問題規模縮小的過程中進行的。 解決技巧：假設已經把所有子問題的最佳結果都計算出來了，那么只需要考慮，如何根據這些子問題的結果來得出最終的答案。 根據動態規劃問題的難易程度，把常見的動態規劃面試題分成如下三大類。 * [ ] 線性規劃 面試題中最常見也是最簡單的一種。 線性，就是說各個子問題的規模以線性的方式分布，并且子問題的最佳狀態或結果可以存儲在一維線性的數據結構里，例如一維數組，哈希表等。 解法中，經常會用 dp[i] 去表示第 i 個位置的結果，或者從 0 開始到第 i 個位置為止的最佳狀態或結果。例如，最長上升子序列。dp[i] 表示從數組第 0 個元素開始到第i個元素為止的最長的上升子序列。 求解 dp[i] 的復雜程度取決于題目的要求，但是基本上有兩種形式。 * [ ] 求解 dp[i] 形式一 第一種形式，當前所求的值僅僅依賴于有限個先前計算好的值，也就是說，dp[i] 僅僅依賴于有限個 dp[j]，其中 j < i。 * 舉例 1：斐波那契數列。 解法：dp[i]=dp[i?1] + dp[i?2]，可以看到，當前值只依賴于前面兩個計算好的值。 建議：LeetCode 第 70 題（爬樓梯）就是一道求解斐波那契數列的題目。 * 舉例2：LeetCode第 198 題，給定一個數組，不能選擇相鄰的數，求如何選才能使總數最大。 解法：這道題需要運用經典的 0-1 思想，簡單說就是：“選還是不選”。 假設 dp[i] 表示到第 i 個元素為止我們所能收獲到的最大總數。 * 如果選擇了第 i 個數，則不能選它的前一個數，因此，收獲的最大總數就是 dp[i?2] + nums[i]。 * 不選，則直接考慮它的前一個數 dp[i?1]。因此，可以推導出它的遞歸公式?dp[i]=max(nums[i] + dp[i?2], dp[i?1])，可以看到，dp[i] 僅僅依賴于有限個 dp[j]，其中 j=i?1，i?2。 代碼實現 ``` public?int?rob(int[]?nums)?{ ????int?n?=?nums.length; ?? ????//?處理當數組為空或者數組只有一個元素的情況 ????if(n?==?0)?return?0; ????if(n?==?1)?return?nums[0]; ????//?定義一個?dp?數組，dp[i]?表示到第?i?個元素為止我們所能收獲到的最大總數 ????int[]?dp?=?new?int[n]; ????//?初始化?dp[0]，dp[1] ????dp[0]?=?nums[0]; ????dp[1]?=?Math.max(nums[0],?nums[1]); ????//?對于每個?nums[i]，考慮兩種情況，選還是不選，然后取最大值 ????for?(int?i?=?2;?i?<?n;?i++)?{ ????????dp[i]?=?Math.max(nums[i]?+?dp[i?-?2],?dp[i?-?1]); ????} ?? ????return?dp[n?-?1]; } ``` * 舉例3：一個機器人位于一個 網格的左上角（起始點在下圖中標記為“Start”）。機器人每次只能向下或向右移動一步。機器人試圖到達網格的右下角（在下圖中標記為“Finish”）。問總共有多少條不同的路徑？ 說明： 和的值均不超過100。 * 解法 1：從起點考慮，暴力法。 * 解法 2：減小問題規模。 分別計算走到它上面的格子以及左邊的格子的步數，相加。遞推公式為?dp[i][j]=dp[i?1][j] + dp[i][j?1]。 雖然利用一個二維數組去保存計算的結果，但是 dp[i][j] 所表達的意思仍然是線性的，dp[i][j] 表示從起點到 (i, j) 的總走法。本題不再討論具體實現。可以看到，dp[i][j] 僅僅依賴于兩個先前的狀態。 * [ ] 求解 dp[i] 形式二 第二種求解 dp[i] 的形式，當前所求的值依賴于所有先前計算好的值，也就是說，dp[i] 是各個 dp[j] 的某種組合，其中 j 由 0 遍歷到 i?1。 舉例：求解最長上升子序列。 解法：dp[i]=max(dp[j]) + 1，0 <= j < i。可以看到，當前值依賴于前面所有計算好的值。 * [ ] 區間規劃 區間規劃，就是說各個子問題的規模由不同的區間來定義，一般子問題的最佳狀態或結果存儲在二維數組里。一般用 dp[i][j] 代表從第 i 個位置到第 j 個位置之間的最佳狀態或結果。 解這類問題的時間復雜度一般為多項式時間，對于一個大小為 n 的問題，時間復雜度不會超過 n 的多項式倍數。例如，O(n)=n^k，k 是一個常數，根據題目的不同而定。 舉例：LeetCode 第 516 題，在一個字符串 S 中求最長的回文子序列。例如給定字符串為 dccac，最長回文就是 ccc。 解法 1： 對于回文來說，必須保證兩頭的字符都相同。用 dp[i][j] 表示從字符串第 i 個字符到第 j 個字符之間的最長回文，比較這段區間外的兩個字符，如果發現它們相等，它們就肯定能構成新的最長回文。而最長的回文長度會保存在 dp[0][n?1] 里。因此，可以推導出如下的遞推公式。 當首尾的兩個字符相等的時候?dp[0][n?1]=dp[1][n?2] + 2， 否則，dp[0][n?1]=max(dp[1][n?1], dp[0][n?2])。 代碼實現 ``` public?static?int?LPS(String?s)?{ ????int?n?=?s.length(); ????//?定義?dp?矩陣，dp[i][j]?表示從字符串第?i?個字符到第?j?個字符之間的最長回文 ????int[][]?dp?=?new?int[n][n]; ?? ????//?初始化?dp?矩陣，將對角線元素設為?1，即單個字符的回文長度為?1 ????for?(int?i?=?0;?i?<?n;?i++)?dp[i][i]?=?1; ?? ????//?從長度為?2?開始，嘗試將區間擴大，一直擴大到?n ????for?(int?len?=?2;?len?<=?n;?len++)?{ ????????//?在擴大的過程中，每次都得出區間的其實位置i和結束位置j ????????for?(int?i?=?0;?i?<?n?-?len?+?1;?i++)?{ ????????????int?j?=?i?+?len?-?1; ?????? ????????????//?比較一下區間首尾的字符是否相等，如果相等，就加2；如果不等，從規模更小的字符串中得出最長的回文長度 ????????????if?(s.charAt(i)?==?s.charAt(j))?{ ????????????????dp[i][j]?=?2?+?(len?==?2???0:?dp[i?+?1][j?-?1]); ??????????????}?else?{ ????????????????dp[i][j]?=?Math.max(dp[i?+?1][j],?dp[i][j?-?1]); ??????????????} ????????} ????} ?? ????return?dp[0][n?-?1]; } ``` 解法 2： 如果用線性規劃的方法來解，假設已經把 S[0]，S[0, 1]，S[0… n?2] 中所有最長的回文子序列都找出來了，把最后一個字符加入到 S 中，能不能成為一個新的最長的回文呢？方法是有的，建議同學們自己嘗試一下。 關于區間規劃，還有很多題目都有用到，例如給定一系列矩陣，求矩陣相乘的總次數最少的相乘方法。? * [ ] 約束規劃 在普通的線性規劃和區間規劃里，一般題目有兩種需求：統計和最優解。 這些題目不會對輸出結果中的元素有什么限制，只要滿足最終的一個條件就好了。但是在很多情況下，題目會對輸出結果的元素添加一定的限制或約束條件，增加了解題的難度。 舉例：0-1 背包問題。 給定 n 個物品，每個物品都有各自的價值 vi 和重量 wi，現在給你一個背包，背包所能承受的最大重量是 W，那么往這個背包里裝物品，問怎么裝能使被帶走的物品的價值總和最大。 因為很多人都熟悉這道經典題目，因此不去詳細講解，但是建議大家好好去做一下這道題。 NP 完全問題 該例題為 NP 完全問題。NP 是 Non-deterministic Polynomial 的縮寫，中文是非決定性多項式。通俗一點來說，對于這類問題，我們無法在多項式時間內解答。這個概念很難，但是理解好它能幫助你很好的分析時間復雜度。 * [ ] 時間復雜度 時間復雜度并不是表示程序解決問題需要花費的具體時間，而是說程序運行的時間隨著問題規模擴大增長的有多快。 如果程序具有 O(1) 的時間復雜度，那么，無論問題規模有多大，運行時間都是固定不變的，這個程序就是一個好程序。如果程序運行的時間隨著問題規模的擴大線性增長，復雜度是 O(n)，也很不錯。還有一些平方數 O(n2)、立方數 O(n3) 的復雜度等，比如冒泡排序。另外還有指數級的復雜度，例如 O(2n)，O(3n) 等。還有甚至 O(n!) 階乘級的復雜度，例如全排列算法。分類如下： * 多項式級別時間復雜度 O(1)、O(n)、O(n×logn)、O(n2)、O(n3) 等，可以表示為 n 的多項式的組合 * 非多項式級別時間復雜度 O(2n)，O(3n) 等指數級別和 O(n!) 等階乘級別 。 * [ ] 例題分析 回到 0-1 背包問題，經典的解法就是利用動態規劃求解，時間復雜度是 O(n×W)。 因為物體的重量 W 是有精度的，如果假設背包的重量是 21.17008，物品的重量精確到了小數點后 5 位，解題的時候，必須對每一個 0.00001 的重量單位分配一個記憶單元，從 0.00000，0.00001，0.00002 一直分配到 21.17008，雖然背包大小只有不到 22，但是一共分配了 210 多萬個單元，這是很可怕的計算量和存儲量。 而計算機都是用二進制來表示一個數，假設涵蓋從 0 到 W 的區間需要 m 位的二進制數，那么 W 就能寫成 2m。因此 0-1 背包問題的復雜度就成為了?O(n×2m)。 現在問題的規模取決于物品的個數以及需要用多少位二進制數來表示背包的重量，很明顯，它是一個指數級的計算量，是一個非多項式級別的復雜度。 #### 結語 這節課后，大家應該能對動態規劃有了比較清晰的認識。學習動態規劃沒有什么捷徑，除了掌握好本節課的知識點，更重要的是多練。