目錄

• 題目描述
• 1、暴力遞歸法的重疊子問題
• 2、備忘錄解法
• 3、dp數組迭代算法
• 4、滾動數組優化
• 5、參考鏈接

題目描述

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項。斐波那契數列的定義如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

1、暴力遞歸法的重疊子問題

暴力遞歸法最為常見，但是同時它的時間復雜度也是最高的，附帶了許多重復計算。

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

畫出遞歸樹：

算法時間復雜度為遞歸二叉樹結點總數，為O(2^n)。f(18)、f(17)被重復計算了，并且以f(18)為根節點的遞歸樹體積也是十分巨大的，如果再算一遍會耗費大量的時間。
這個問題性質我們可以描述為“重疊子問題”。

2、備忘錄解法

既然是重復計算的問題，我們就可以構造一個備忘錄。
每次計算出某個子問題的答案先別著急返回，先記到備忘錄中再返回；
每次遇到一個子問題，先去備忘錄中查找，如果已經解決了這個問題，就直接把答案拿過來用，不再進行計算。

class Solution { public:int search_helperTab(vector<int >& helperTab,int n){//n較小的直接返回if(n == 1 || n == 2) return 1;//如果已經計算過了，直接返回計算過的值if(helperTab[n] != 0) return helperTab[n];//如果沒有計算過，則需要重新計算一遍else{helperTab[n] = (search_helperTab(helperTab,n-1) + search_helperTab(helperTab,n-2))%1000000007;}return helperTab[n];}int fib(int n) {if(n==0) return 0;//構建一個備忘錄vector<int >helperTab(n+1,0);return search_helperTab(helperTab,n);} };

帶備忘錄的遞歸算法，將一顆存在巨量冗余的遞歸樹剪枝為沒有冗余的遞歸圖。
遞歸算法時間復雜度=子問題個數 * 解決子問題所需要的時間。
由于不存在冗余計算，所以子問題個數為O(n);解決一個子問題的時間是O(1);
所以本算法的時間復雜度是O(n)。
注意，我們剛剛畫的遞歸樹是從上向下延伸的，都是從一個規模較大的原問題，向下逐漸分解規模，直到觸底(f(1)、f(2)),然后逐層返回答案，這就是自頂向下。

如果直接從最底下的最小規模的f(1)、f(2)開始往上推導，直到f(20),這就是動態規劃的思路。

3、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);dp[1]=dp[2]=1;for(int i = 3;i <= n;i++)dp[i]=(dp[i-1]+dp[i-2])%1000000007;return dp[n];} };

4、滾動數組優化

狀態方程中的當前狀態只由前兩個狀態決定，所以不需要一個數組進行存放。

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

這樣空間復雜度就降到O(1)了。

5、參考鏈接

劍指 Offer 10- I. 斐波那契數列
labuladong：動態規劃詳解（修訂版）

總結

以上是生活随笔為你收集整理的剑指 Offer 10- I. 斐波那契数列 （从重叠子问题到备忘录到dp数组迭代解法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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