```c++
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[10000001]; // 记忆化搜索
ll fb(ll x){
    if(dp[x]) return dp[x]; // 如果曾经被记录过，直接返回
    if(x<=2){
        return 1;
    }
    return dp[x]=fb(x-1)+fb(x-2); // 返回的同时记录
}
int main(){
    ll n;
    cin>>n;
    cout<<fb(n);
    return 0;
}
```

你这个的时间复杂度约为 $O(1.618^n)$，会超时。
建议学习一下记忆化或递推。

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

斐波那契记忆化

真奇怪，TLE了

#include<bits/stdc++.h>
using namespace std;
int fb(int x){
if(x<=2){
return 1;
}
return fb(x-1)+fb(x-2);
}
int main(){


全部评论 3