斐波那契数列

编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）(n < 40)。
数列描述：
f1=f2==1;
fn=fn-1+fn-2(n>=3)。
代码如下：
#include<iostream>
using namespace std;
int fib(int n){
    if(n==1||n==2){
    return 1;
}
    return fib(n-1)+fib(n-2);
}
int main(){
    int n;
    while(cin>>n){
    cout<<fib(n)<<endl;
    }
    return 0;
}
如果限制范围，需要记忆化递归，防止重复：
#include<iostream>
using namespace std;
long long fib(int n,long long memo[]){//记忆化递归
    if(n==1||n==2){
    return 1;
}
    if(memo[n]!=0){
        return memo[n];
    }
    memo[n]=fib(n-1,memo)+fib(n-2,memo);
    return memo[n];
}
int main(){
    int n;
    while(cin>>n){
        long long memo[71]={0};
    cout<<fib(n,memo)<<endl;
    }
    return 0;
}
记忆化递归通过「数组 memo 缓存已计算的结果」，后续遇到相同子问题直接读取缓存，时间复杂度优化为 \(O(n)\)，空间复杂度 \(O(n)\)（递归栈 + 缓存数组）。