一、題目描述
寫一個函數，輸入n，求斐波拉契數列的第n項。斐波拉契數列定義如下：
f(n) = {
0 n=0
1 n=1
f(n-1)+f(n-1) n>1
}
二、解題思路
【解法一】常規遞歸
不足：此法不推薦，原因是會產生大量重複的計算，而且重複的結點會隨著n的增大而急劇增加。
事實上，用遞歸方法計算的時間複雜度是以n的指數方法遞增的
【解法二】帶備忘錄的遞歸
此法在解法一的基礎上加了一個存儲，避免了大量重複結點的計算，比法一效率高很多
【解法三】動態規劃
此題滿足動規的特點：新問題依賴子問題。於是考慮可自底向上的思考方式：
首先根據f(0)和f(1)得到f(2)
然後根據f(1)和f(2)得到f(3)
...
以此類推，最後得到f(n),可保證一次for循環得出結果，所以複雜度為O(n)
三、算法實現
方法1：常規遞歸--不推薦
方法2：帶備忘錄的遞歸
方法3：動態規劃
分享到:
閱讀更多 CSDN學院 的文章
