【递归】斐波那契数

#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;
}
1709081489265.webp

数据量大时,不适宜使用递归,而是使用动态规划(备忘录)。

#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
点赞15 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容