接上文：【README1】動態規劃之解題思路

文章目錄

• 斐波那契數列講解——解決重疊子問題
• • （1）暴力遞歸
  • （2）帶有備忘錄的遞歸解法
  • （3）自底向上——dp數組解法
  • （4）總結：狀態轉移方程
  • （5）狀態壓縮

斐波那契數列講解——解決重疊子問題

所有的理論都需要實際的題目來驗證，這里我們不選那些經典的動態規劃的題目，因為我們只求抓住最本質，把這個思路講解清楚，而斐波那契數列就是這樣一個很好的例子，當然它并不算是一個非常典型的動態規劃的題目。

LeetCode 509：斐波那契數列

接下來，我們會用各個方面來闡述，從時間復雜度最高的遞歸，再到備忘錄和dp數組的解決，逐步講解動態規劃中我們應該怎么去想和怎么優化

（1）暴力遞歸

斐波那契數列是一個典型的遞歸題目，它的寫法非常簡單，這里我就不多強調了

class Solution { public:int fib(int n) {if (n==0) return 0;if (n==1 || n==2) return 1;return fib(n-1)+fib(n-2);} };

題目可以通過，但是時間高的嚇人

為什么這么慢呢？其實這就是動態規劃的第一個大的問題——重疊子問題

我們知道遞歸問題本質就是二叉樹的問題，所以在遞歸的過程中就是在遍歷一顆二叉樹，所以這種接法對應的遞歸樹是這樣的

很顯然，想要計算fib(20)，就先要計算fib(19)和fib(18)，計算fib(19)又要計算fib(18)和fib(17)…可以看出圖中的f(18),f(17)很顯然是不需要計算的，雖然圖中只畫出了一點，但是你應該明白，這顆遞歸樹要是完全展開，那是很恐怖的。所以這個算法極其低效

（2）帶有備忘錄的遞歸解法

既然耗時的原因是因為重疊子問題太多，那么不如這樣：把fib(18)計算完之后，存儲在一個備忘錄中，下次只要需要求解fib(18)，直接從備忘錄里面拿多好。
而實現備忘錄，我們更多用數組，當然你也可以用哈希表，道理是一樣的。

class Solution { public:int back(vector<int>& memory,int n){if(n==1 || n==2) return 1;if(memory[n]!=0) return memory[n];//一旦對應位置不等于0，表示已經計算過了，立馬直接返回結果即可return back(memory,n-1)+back(memory,n-2);}int fib(int n) {if (n==0) return 0;vector<int> memory(n+1,0);//設立一個備忘錄，初始狀態設置為0，0表示該位置的元素沒有被記錄在備忘錄上return back(memory,n);} };

繼續觀察這種算法的遞歸樹，如下，你可以很明顯的發現，這種帶備忘錄的解法就是我們經常說的“剪枝”操作，以下把一顆非常冗余的樹修剪的很干凈，或者說就是減少了重疊子問題

如下，很明顯它的時間復雜度要低

至此，這種算法的效率已經能符合動態規劃相應的題目的效率要求了。但是我們現在的解決時自頂向下，而一般的動態規劃的題目時自底向上的。

• 自頂向下：從一個原始的問題，也就是規模較大的問題，比如說fib(20)，逐步向下分解，分解到很小的規模,一直分解到再不能分解為止，比如fib(1)和fib(2)這兩個base case
• 自底向上：反過來，從最下面，最簡單的情況如上，進行反推得到結果。我們動態規劃就是按照這種思路來的

（3）自底向上——dp數組解法

我們把上面的備忘錄變成一個dp數組，通過dp數組不斷迭代向上求解。

class Solution { public:int fib(int n) {if(n==0) return 0;if(n==1 || n==2) return 1;vector<int> dp(n+1,0);//最簡單的情況，base casedp[1]=1;dp[2]=1;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];} };

你會很明顯發現，這樣的結局效率非常的高

同時這種算法對應的圖和帶備忘錄的遞歸算法的那張圖結果相反

（4）總結：狀態轉移方程

其實在這個過程中，我們已經不知不覺的使用了狀態轉移方程。如下，

你可以把f(n)當作一個狀態，而這個狀態n是由狀態n-1和狀態n-2進行相加操作轉移過來的，僅此而已。所以代碼中的dp[i]=dp[i-1]+dp[i-2]就是這個意思

那么如何得出狀態轉移方程呢？其實完全依賴的就是咋們的暴力解法，暴力解法代表的就是狀態轉移方程，一旦動態規劃的題目中你能寫出暴力解法，那么剩余的操作無非就是備忘錄或dp數組優化了。也就是先自頂向下，再自底向上

（5）狀態壓縮

至此我們已經解決了重疊子問題，關于如何解決最優子結構會在下篇文章中說明。
對于剛才的例子，還能繼續進行優化，就是優化空間，因為在這個斐波那契數列中，當前狀態僅僅和前兩個狀態有關，而前面無關，所以我們可以優化空間，不采用數組，直接兩個變量，交替保存。

class Solution { public:int fib(int n) {if (n==0) return 0;if (n==1 || n==2) return 1;int prev=1;int curr=1;for(int i=3;i<=n;i++){int sum=prev+curr;prev=curr;curr=sum;}return curr;} };

所以如果我們發現每次狀態轉移的時候只需要dp數組中的一部分，那么就可以嘗試采用狀態壓縮來壓縮dp table的大小，只記錄必要的數據

總結

以上是生活随笔為你收集整理的【README2】动态规划之斐波那契数列说明重叠子问题如何解决的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。