動態規劃 · ttttt

# 動態規劃 # 遞歸和動態規劃動態規劃可以理解為是**查表的遞歸（記憶化）**。那么什么是遞歸？什么是查表（記憶化）？ ## 遞歸遞歸是指在函數的定義中使用函數自身的方法。算法中使用遞歸可以很簡單地完成一些用循環實現的功能，比如二叉樹的左中右序遍歷。遞歸在算法中有非常廣泛的使用，包括現在日趨流行的函數式編程。有意義的遞歸算法會把問題分解成規模縮小的同類子問題，當子問題縮減到尋常的時候，就可以知道它的解。然后建立遞歸函數之間的聯系即可解決原問題，這也是我們使用遞歸的意義。準確來說，遞歸并不是算法，它是和迭代對應的一種編程方法。只不過，由于隱式地借助了函數調用棧，因此遞歸寫起來更簡單。一個問題要使用遞歸來解決必須有遞歸終止條件（算法的有窮性）。雖然以下代碼也是遞歸，但由于其無法結束，因此不是一個有效的算法： ``` <pre class="calibre18">``` def f(n): return n + f(n - 1) ``` ``` 更多的情況應該是： ``` <pre class="calibre18">``` def f(n): if n == 1: return 1 return n + f(n - 1) ``` ``` ### 練習遞歸一個簡單練習遞歸的方式是將你寫的迭代全部改成遞歸形式。比如你寫了一個程序，功能是“將一個字符串逆序輸出”，那么使用迭代將其寫出來會非常容易，那么你是否可以使用遞歸寫出來呢？通過這樣的練習，可以讓你逐步適應使用遞歸來寫程序。如果你已經對遞歸比較熟悉了，那么我們繼續往下看。 ### 遞歸中的重復計算遞歸中可能存在這么多的重復計算，為了消除這種重復計算，一種簡單的方式就是記憶化遞歸。即一邊遞歸一邊使用“記錄表”（比如哈希表或者數組）記錄我們已經計算過的情況，當下次再次碰到的時候，如果之前已經計算了，那么直接返回即可，這樣就避免了重復計算。而**動態規劃中 DP 數組其實和這里“記錄表”的作用是一樣的**。 ### 遞歸的時間復雜度分析敬請期待我的新書。 ### 小結使用遞歸函數的優點是邏輯簡單清晰，缺點是過深的調用會導致棧溢出。這里我列舉了幾道算法題目，這幾道算法題目都可以用遞歸輕松寫出來： - 遞歸實現 sum - 二叉樹的遍歷 - 走樓梯問題 - 漢諾塔問題 - 楊輝三角當你已經適應了遞歸的時候，那就讓我們繼續學習動態規劃吧！ ## 動態規劃如果你已經熟悉了遞歸的技巧，那么使用遞歸解決問題非常符合人的直覺，代碼寫起來也比較簡單。這個時候我們來關注另一個問題 - **重復計算** 。我們可以通過分析（可以嘗試畫一個遞歸樹），可以看出遞歸在縮小問題規模的同時**是否可能會重復計算**。 [279.perfect-squares](279.perfect-squares.html) 中我通過遞歸的方式來解決這個問題，同時內部維護了一個緩存來存儲計算過的運算，這么做可以減少很多運算。這其實和動態規劃有著異曲同工的地方。 > 小提示：如果你發現并沒有重復計算，那么就沒有必要用記憶化遞歸或者動態規劃了。因此動態規劃就是枚舉所以可能。不過相比暴力枚舉，動態規劃不會有重復計算。因此如何保證枚舉時不重不漏是關鍵點之一。遞歸由于使用了函數調用棧來存儲數據，因此如果棧變得很大，那么會容易爆棧。 ### 爆棧我們結合求和問題來講解一下，題目是給定一個數組，求出數組中所有項的和，要求使用遞歸實現。代碼： ``` <pre class="calibre18">``` function sum(nums) { if (nums.length === 0) return 0; if (nums.length === 1) return nums[0]; return nums[0] + sum(nums.slice(1)); } ``` ``` 我們用遞歸樹來直觀地看一下。 ![](https://img.kancloud.cn/53/0a/530a8977ce3405c5603595fd85ee7786_828x537.jpg) 這種做法本身沒有問題，但是每次執行一個函數都有一定的開銷，拿 JS 引擎執行 JS 來說，每次函數執行都會進行入棧操作，并進行預處理和執行過程，所以內存會有額外的開銷，數據量大的時候很容易造成爆棧。 > 瀏覽器中的 JS 引擎對于代碼執行棧的長度是有限制的，超過會爆棧，拋出異常。 ### 重復計算我們再舉一個重復計算的例子，問題描述：一個人爬樓梯，每次只能爬 1 個或 2 個臺階，假設有 n 個臺階，那么這個人有多少種不同的爬樓梯方法？ > [746. 使用最小花費爬樓梯](https://leetcode-cn.com/problems/min-cost-climbing-stairs/) 是這道題的換皮題， GrowingIO 前端工程師崗位考察過這個題目。由于上第 n 級臺階一定是從 n - 1 或者 n - 2 來的，因此上第 n 級臺階的數目就是 `上 n - 1 級臺階的數目加上 n - 1 級臺階的數目`。遞歸代碼： ``` <pre class="calibre18">``` function climbStairs(n) { if (n === 1) return 1; if (n === 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); } ``` ``` 我們繼續用一個遞歸樹來直觀感受以下： ![](https://img.kancloud.cn/be/b1/beb1e955a9930bfc3af6fe7deab0d9fc_827x398.jpg) > 紅色表示重復的計算可以看出這里面有很多重復計算，我們可以使用一個 hashtable 去緩存中間計算結果，從而省去不必要的計算。那么動態規劃是怎么解決這個問題呢？答案也是“查表”，不過區別于遞歸使用函數調用棧，動態規劃通常使用的是 dp 數組，數組的索引通常是問題規模，值通常是遞歸函數的返回值。`遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。動態規劃是從尋常入手，逐步擴大規模到最優子結構。` 如果上面的爬樓梯問題，使用動態規劃，代碼是這樣的： ``` <pre class="calibre18">``` function climbStairs(n) { if (n == 1) return 1; const dp = new Array(n); dp[0] = 1; dp[1] = 2; for (let i = 2; i < n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[dp.length - 1]; } ``` ``` 不會也沒關系，我們將遞歸的代碼稍微改造一下。其實就是將函數的名字改一下： ``` <pre class="calibre18">``` function dp(n) { if (n === 1) return 1; if (n === 2) return 2; return dp(n - 1) + dp(n - 2); } ``` ``` > dp\[n\] 和 dp(n) 對比看，這樣是不是有點理解了呢? 只不過遞歸用調用棧枚舉狀態，而動態規劃使用迭代枚舉狀態。動態規劃的查表過程如果畫成圖，就是這樣的： ![](https://img.kancloud.cn/f2/ef/f2ef7fa8ec597f73e4c84238ad14920b_832x443.jpg) > 虛線代表的是查表過程這道題目是動態規劃中最簡單的問題了，因為設計到單個因素的變化，如果涉及到多個因素，就比較復雜了，比如著名的背包問題，挖金礦問題等。對于單個因素的，我們最多只需要一個一維數組即可，對于如背包問題我們需要二維數組等更高緯度。爬樓梯我們并沒有必要使用一維數組，而是借助兩個變量來實現的，空間復雜度是 O(1)。代碼： ``` <pre class="calibre18">``` function climbStairs(n) { if (n === 1) return 1; if (n === 2) return 2; let a = 1; let b = 2; let temp; for (let i = 3; i <= n; i++) { temp = a + b; a = b; b = temp; } return temp; } ``` ``` 之所以能這么做，是因為爬樓梯問題的狀態轉移方程中**當前狀態只和前兩個狀態有關**，因此只需要存儲這兩個即可。動態規劃問題有很多這種討巧的方式，這個技巧叫做滾動數組。再次強調一下： - 如果說遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。那么動態規劃就是從尋常入手，逐步擴大規模到最優子結構。 - 記憶化遞歸和動態規劃沒有本質不同。都是枚舉狀態，并根據狀態直接的聯系逐步推導求解。 - 動態規劃性能通常更好。一方面是遞歸的棧開銷，一方面是滾動數組的技巧。 ### 動態規劃的三個要素 1. 狀態轉移方程 2. 臨界條件 3. 枚舉狀態 > 可以看出，用遞歸解決也是一樣的思路在上面講解的爬樓梯問題中，如果我們用 f(n) 表示爬 n 級臺階有多少種方法的話，那么： ``` <pre class="calibre18">``` f(1) 與 f(2) 就是【邊界】 f(n) = f(n-1) + f(n-2) 就是【狀態轉移公式】 ``` ``` 我用動態規劃的形式表示一下： ``` <pre class="calibre18">``` dp[0] 與 dp[1] 就是【邊界】 dp[n] = dp[n - 1] + dp[n - 2] 就是【狀態轉移方程】 ``` ``` 可以看出兩者是多么的相似。實際上臨界條件相對簡單，大家只有多刷幾道題，里面就有感覺。困難的是找到狀態轉移方程和枚舉狀態。這兩個核心點的都建立在**已經抽象好了狀態**的基礎上。比如爬樓梯的問題，如果我們用 f(n) 表示爬 n 級臺階有多少種方法的話，那么 f(1), f(2), ... 就是各個**獨立的狀態**。不過狀態的定義都有特點的套路。比如一個字符串的狀態，通常是 dp\[i\] 表示字符串 s 以 i 結尾的 ....。比如兩個字符串的狀態，通常是 dp\[i\]\[j\] 表示字符串 s1 以 i 結尾，s2 以 j 結尾的 ....。當然狀態轉移方程可能不止一個，不同的轉移方程對應的效率也可能大相徑庭，這個就是比較玄學的話題了，需要大家在做題的過程中領悟。搞定了狀態的定義，那么我們來看下狀態轉移方程。 #### 狀態轉移方程爬樓梯問題由于上第 n 級臺階一定是從 n - 1 或者 n - 2 來的，因此上第 n 級臺階的數目就是 `上 n - 1 級臺階的數目加上 n - 1 級臺階的數目`。上面的這個理解是核心，它就是我們的狀態轉移方程，用代碼表示就是 `f(n) = f(n - 1) + f(n - 2)`。實際操作的過程，有可能題目和爬樓梯一樣直觀，我們不難想到。也可能隱藏很深或者維度過高。如果你實在想不到，可以嘗試畫圖打開思路，這也是我剛學習動態規劃時候的方法。當你做題量上去了，你的題感就會來，那個時候就可以不用畫圖了。狀態轉移方程實在是沒有什么靈丹妙藥，不同的題目有不同的解法。狀態轉移方程同時也是解決動態規劃問題中最最困難和關鍵的點，大家一定要多多練習，提高題感。接下來，我們來看下不那么困難，但是新手疑問比較多的問題 - **如何枚舉狀態**。 #### 如何枚舉狀態前面說了如何枚舉狀態，才能不重不漏是枚舉狀態的關鍵所在。 - 如果是一維狀態，那么我們使用一層循環可以搞定。 - 如果是兩維狀態，那么我們使用兩層循環可以搞定。 - 。。。這樣可以保證不重不漏。但是實際操作的過程有很多細節比如: - 一維狀態我是先枚舉左邊的還是右邊的？（從左到右遍歷還是從右到左遍歷） - 二維狀態我是先枚舉左上邊的還是右上的，還是左下的還是右下的？ - 里層循環和外層循環的位置關系（可以互換么） - 。。。其實這個東西和很多因素有關，很難總結出一個規律，而且我認為也完全沒有必要去總結規律。不過這里我還是總結了一個關鍵點，那就是： - **如果你沒有使用滾動數組的技巧**，那么遍歷順序取決于狀態轉移方程。比如: ``` <pre class="calibre18">``` for i in range(1, n + 1): dp[i] = dp[i - 1] + 1; ``` ``` 那么我們就需要從左到右遍歷，原因很簡單，因為 dp\[i\] 依賴于 dp\[i - 1\]，因此計算 dp\[i\] 的時候， dp\[i - 1\] 需要已經計算好了。 > 二維的也是一樣的，大家可以試試。 - **如果你使用了滾動數組的技巧**，則怎么遍歷都可以，但是不同的遍歷意義通常不不同的。比如我將二維的壓縮到了一維： ``` <pre class="calibre18">``` for i in range(1, n + 1): for j in range(1, n + 1): dp[j] = dp[j - 1] + 1; ``` ``` 這樣是可以的。 dp\[j - 1\] 實際上指的是壓縮前的 dp\[i\]\[j - 1\] 而： ``` <pre class="calibre18">``` for i in range(1, n + 1): # 倒著遍歷 for j in range(n, 0, -1): dp[j] = dp[j - 1] + 1; ``` ``` 這樣也是可以的。但是 dp\[j - 1\] 實際上指的是壓縮前的 dp\[i - 1\]\[j - 1\]。因此實際中采用怎么樣的遍歷手段取決于題目。我特意寫了一個 [【完全背包問題】套路題（1449. 數位成本和為目標值的最大數字](https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/solution/wan-quan-bei-bao-wen-ti-tao-lu-ti-1449-shu-wei-che/) 文章，通過一個具體的例子告訴大家不同的遍歷有什么實際不同，強烈建議大家看看，并順手給個三連。 - 關于里外循環的問題，其實和上面原理類似。這個比較微妙，大家可以參考這篇文章理解一下 [0518.coin-change-2](518.coin-change-2.html)。 #### 小結關于如何確定臨界條件通常是比較簡單的，多做幾個題就可以快速掌握。關于如何確定狀態轉移方程，這個其實比較困難。不過所幸的是，這些套路性比較強，比如一個字符串的狀態，通常是 dp\[i\] 表示字符串 s 以 i 結尾的 ....。比如兩個字符串的狀態，通常是 dp\[i\]\[j\] 表示字符串 s1 以 i 結尾，s2 以 j 結尾的 ....。這樣遇到新的題目可以往上套，實在套不出那就先老實畫圖，不斷觀察，提高題感。關于如何枚舉狀態，如果沒有滾動數組，那么根據轉移方程決定如何枚舉即可。如果用了滾動數組，那么要注意壓縮后和壓縮前的 dp 對應關系即可。 ### 動態規劃為什么要畫表格動態規劃問題要畫表格，但是有的人不知道為什么要畫，就覺得這個是必然的，必要要畫表格才是動態規劃。其實動態規劃本質上是將大問題轉化為小問題，然后大問題的解是和小問題有關聯的，換句話說大問題可以由小問題進行計算得到。這一點是和用遞歸解決一樣的，但是動態規劃是一種類似查表的方法來縮短時間復雜度和空間復雜度。畫表格的目的就是去不斷推導，完成狀態轉移，表格中的每一個 cell 都是一個`小問題`，我們填表的過程其實就是在解決問題的過程，我們先解決規模為尋常的情況，然后根據這個結果逐步推導，通常情況下，表格的右下角是問題的最大的規模，也就是我們想要求解的規模。比如我們用動態規劃解決背包問題，其實就是在不斷根據之前的小問題`A[i - 1][j] A[i -1][w - wj]`來詢問： - 應該選擇它 - 還是不選擇它至于判斷的標準很簡單，就是價值最大，因此我們要做的就是對于選擇和不選擇兩種情況分別求價值，然后取最大，最后更新 cell 即可。其實大部分的動態規劃問題套路都是“選擇”或者“不選擇”，也就是說是一種“選擇題”。并且大多數動態規劃題目還伴隨著空間的優化（滾動數組），這是動態規劃相對于傳統的記憶化遞歸優勢的地方。除了這點優勢，就是上文提到的使用動態規劃可以減少遞歸產生的函數調用棧，因此性能上更好。 ### 相關問題 - [0091.decode-ways](91.decode-ways.html) - [0139.word-break](139.word-break.html) - [0198.house-robber](198.house-robber.html) - [0309.best-time-to-buy-and-sell-stock-with-cooldown](309.best-time-to-buy-and-sell-stock-with-cooldown.html) - [0322.coin-change](322.coin-change.html) - [0416.partition-equal-subset-sum](416.partition-equal-subset-sum.html) - [0518.coin-change-2](518.coin-change-2.html) ## 總結本篇文章總結了算法中比較常用的兩個方法 - 遞歸和動態規劃。遞歸的話可以拿樹的題目練手，動態規劃的話則將我上面推薦的刷完，再考慮去刷力扣的動態規劃標簽即可。大家前期學習動態規劃的時候，可以先嘗試使用記憶化遞歸解決。然后將其改造為動態規劃，這樣多練習幾次就會有感覺。之后大家可以練習一下滾動數組，這個技巧很有用，并且相對來說比較簡單。比較動態規劃的難點在于**枚舉所以狀態（無重復）** 和 **尋找狀態轉移方程**。如果你只能記住一句話，那么請記住：`遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。動態規劃是從尋常入手，逐步擴大規模到最優子結構。` 另外，大家可以去 LeetCode 探索中的 [遞歸 I](https://leetcode-cn.com/explore/orignial/card/recursion-i/) 中進行互動式學習。