劍指 offer 面試題精選圖解 10-I.斐波那契數(shù)列
大家好，我是程序員吳師兄，歡迎來(lái)到圖解劍指 Offer 專欄，在這個(gè)專欄里我將和大家一起學(xué)習(xí)如何用合理的思維來(lái)思考、解題、寫代碼。
今天分享的題目來(lái)源于 LeetCode 上的劍指 Offer 系列 面試題10- I. 斐波那契數(shù)列。
題目鏈接：https://www.algomooc.com/229.html
一、題目描述
寫一個(gè)函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項(xiàng)。斐波那契數(shù)列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。
答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。
示例 1：
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5
提示：
0 <= n <= 100
二、題目解析
似乎學(xué)校的老師講 遞歸 的時(shí)候都喜歡拿 斐波那契數(shù)列 舉例。
因?yàn)?，很容易就寫出下面的代碼。
class Solution {
public int fib(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return (fib(n-1) + fib(n-2)) % 1000000007;
}
}
結(jié)果也很明顯，無(wú)腦的遞歸暴力解法包含了大量的重復(fù)計(jì)算，提交上去直接標(biāo)紅提示超出時(shí)間限制。
舉個(gè)例子，n = 10。
接下來(lái)，我們依舊用 四步分析法 來(lái)分析一下這道題目。
模擬：模擬題目的運(yùn)行。 規(guī)律：嘗試總結(jié)出題目的一般規(guī)律和特點(diǎn)。 匹配：找到符合這些特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)與算法。 邊界：考慮特殊情況。
1、模擬
觀察遞歸樹，不難發(fā)現(xiàn)，在這棵樹上有 很多結(jié)點(diǎn)是重復(fù)的 ，而且重復(fù)的結(jié)點(diǎn)數(shù)會(huì)隨著 n 的增大而急劇增加，比如 fib(8) 被計(jì)算了兩次，并且，以 fib(8) 為根的這個(gè)遞歸樹體量巨大，多算一遍，會(huì)耗費(fèi)巨大的時(shí)間。
事實(shí)上，用遞歸方法計(jì)算的時(shí)間復(fù)雜度是以 n 的指數(shù)的方式遞增的。
2、規(guī)律
即然耗時(shí)的原因是重復(fù)計(jì)算，我們只要想辦法避免重復(fù)計(jì)算就行了。
如何避免重復(fù)計(jì)算？
找一個(gè)合適的 數(shù)據(jù)結(jié)構(gòu) 在遞歸的過(guò)程中存儲(chǔ)計(jì)算的值，重復(fù)遇到某數(shù)字則直接從該 數(shù)據(jù)結(jié)構(gòu) 中取用，避免重復(fù)計(jì)算。
3、匹配
這個(gè)合適的數(shù)據(jù)結(jié)構(gòu)可以用 數(shù)組 。
4、邊界
初始情況只有一個(gè)數(shù)或者兩個(gè)數(shù)
三、動(dòng)畫理解
四、參考代碼
//訪問網(wǎng)站，獲取更多題解：https://www.algomooc.com
class Solution {
public int fib(int n) {
//邊界判斷
if(n == 0) return 0;
//用于存儲(chǔ)第 0 到 n 個(gè)數(shù)對(duì)應(yīng)的值
int[] dp = new int[n + 1];
//先定義好第一個(gè)數(shù)
dp[0] = 0;
//再定義好第二個(gè)數(shù)
dp[1] = 1;
//計(jì)算大于 0 和大于 1 的值
for(int i = 2; i <= n; i++){
//當(dāng)遇到之前計(jì)算過(guò)的數(shù)時(shí)，將不再遞歸往下找，直接用記憶化結(jié)果
dp[i] = dp[i-1] + dp[i-2];
//題目要求進(jìn)行取模處理
dp[i] %= 1000000007;
}
//返回結(jié)果
return dp[n];
}
}
五、復(fù)雜度分析
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度為 O(N) 。
空間復(fù)雜度
空間復(fù)雜度為 O(N)。
六、相關(guān)標(biāo)簽
遞歸 記憶化 備忘錄 動(dòng)態(tài)規(guī)劃
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
專注服務(wù)器后臺(tái)技術(shù)棧知識(shí)總結(jié)分享
歡迎關(guān)注交流共同進(jìn)步