題目鏈接：斐波那契數列 - 題目 - 青藤 OJ

題目來源：經典題

---

題目大意

輸入

，輸出 0，1 開頭的斐波那契數列的第 n 項。

這里我們不討論遞推方法，我們采用這道簡單的題目簡單說一下記憶化搜索相關內容。

解法

首先，基礎的遞歸解決的程序非常好寫，對于 f(n) 來說

• 邊界情況：
• 遞歸方程：

所以代碼就很自然

#include <bits/stdc++.h> using namespace std; long long f(int n) {if (n == 1)return 0;if (n == 2)return 1;return f(n - 1) + f(n - 2); } int main() {int n;cin >> n;cout << f(n) << endl;return 0; }

然而這樣的做法，在 n 為 40 時便達到了 500ms，在 45 時無法通過，為什么呢？

我們會發現，求解 f(6) 時 用到的 f(4) 會在求解 f(5) 用到時重新求解，再往上看的話，重復計算所花的時間時非常恐怖的，導致我們做了很多多余的計算。

解決的方法也很簡單，算過了的我們就拿個小本本出來記下來，下次要用上直接拿出上次的結果就好。

#include <bits/stdc++.h> using namespace std; long long book[50]; //小本本 long long f(int n) {//如果算過了，直接返回結果if (book[n] != -1)return book[n];if (n == 1) {//返回之前記下來book[n] = 0;return book[n];}if (n == 2) {//返回之前記下來book[n] = 1;return 1;}//返回之前記下來book[n] = f(n - 1) + f(n - 2);return book[n]; } int main() {//沒算過的就用-1表示memset(book, -1, sizeof(book));int n;cin >> n;cout << f(n) << endl;return 0; }

這便是所謂的記憶化遞歸。如果有兩個參數的遞歸我們可以開一個二維數組來記錄就好。

比如下面這道：阿克曼(Ackmann)函數 - 題目 - 青藤 OJ

雖然這道題的數據范圍不需要記憶化，普通遞歸也能過，但是大家可以試一下用記憶化遞歸實現~

當然斐波那契數列的求解還會有更多方式，遞推的方式就可以和記憶化遞歸一樣達到

的時間復雜度，采用矩陣快速冪來做的話可以達到 ，也會有數學的方法，利用公式快速得出更大數據范圍的項。

總結

以上是生活随笔為你收集整理的利用一维数组求菲波那契数列前40项的和并输出结果。_[W2D2]斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

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