一起学习交流~

斐波那契数列-dp重叠子问题入门

算法 laomuji 8个月前 (01-16) 342次浏览 已收录 0个评论

解释

斐波那契数列是个很经典的递归题目,但是使用递归会很慢,所以用数组保存运算结果 可以极大优化速度,把2^n的时间复杂度优化为n,实际上这就是动态规划 重叠子问题的解法,利用空间换时间.

解法

暴力

int fib(int n) {
    if(n<2)return n;//0或者1直接返回
    return fib(n - 1) + fib(n - 2);
}

dp

    int fib(int n) {
        if(n<2)return n;//0 1
        vector<int>nums={0,1};
        for(int i =2;i<=n;i++){
            nums.push_back((nums[i-1]+nums[i-2]);
        }
        return nums[nums.size()-1];
    }

dp状态压缩

    //0 1 1 2 3 5 8
    //滚动数组
    //c=a+b
    //a=b
    //b=c
    int fib(int n) {
        if(n<2)return n;
        n++;
        int a = 0,b=1,c=0;
        for(int i=2;i<n;i++){
            c = a+b;
            a=b;
            b=c;
        }
        return c;
    }
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论