#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;
}
© 版权声明
若无特殊说明,文章版权归作者所有,请勿转载至任何平台。
THE END
暂无评论内容