题解 | Fibonacci

#include<iostream>
using namespace std;

const int MAX = 40;
long long f[MAX];
bool isVisit[MAX];

long long Fibonacci(int n) {
    if (n == 0) { // 递归出口
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (isVisit[n]) {
        return f[n];
    } else {// 主体
        f[n] =  Fibonacci(n - 1) + Fibonacci(n - 2);
        isVisit[n] = true;

        return f[n];
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        isVisit[i] = false;
    }
    // 下面的初始化可以去掉
    isVisit[0] = true;
    f[0] = 0;
    isVisit[1] = true;
    f[1] = 1;

    int n;
    while (cin >> n) {
        cout << Fibonacci(n) << endl;
    }

}