【递归】斐波那契数

#include<iostream>
using namespace std;
int fib(int n){
    if (n<2){
        return n;
    }
    return fib(n-1) + fib(n-2);
}
int main(){
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

数据量大时，不适宜使用递归，而是使用动态规划（备忘录）。

#include<iostream>
#include<vector>
using namespace std;
​
vector<int> dp;
int f(int n){
    if (dp[n]){  // 记忆化递归
        return dp[n];
    }
    if (n<2){
        return dp[n] = n;
    }
    return dp[n] = f(n-1) + f(n-2);
}
int fib(int n){
    dp.resize(n+1, 0);  // 重新定义dp大小，初始化为0
    return f(n);
}
int main(){
    int times;
    cin >> times;
    while (times--){
        int n;
        cin >> n;
        cout << fib(n) << endl;
    }
    return 0;
}