斐波那契数列:动态规划

初识动态规划

在通过递归和记忆化搜索解决斐波那契数列后,我们现在来看看如何通过动态规划计算斐波那契数列。

动态规划

什么是动态规划

对于斐波那契数列,如果使用单纯的递归算法,会导致冗余计算的增长是“爆炸性”的。于是我们用记忆化搜索,新建一个用于存储“已经解决过的子问题”的表以避免冗余计算。

而记忆化存储,其实也算动态规划的一种。动态规划(dynamic programming,俗称dp)基本上就是基于将递归算法重新写成非递归算法,并将子问题的答案系统的记录在表中。

斐波那契数列:动态规划

将递归方程转换为非递归方程

斐波那契的递归方程为:

F(n)=F(n-1)+F(n-2)

说白了就是xxx的前两项之和等于xxx。那我们用单个循环不就能解决了吗?把斐波那契数列当作一个数组。这里用leetcode官方题解的gif作为示例

#include<iostream>
#include<vector>
using namespace std;

int fib(int n)
{
    if(n<=1)
    {
        return n;
    }
    int left=0,right=1;
    int result=0;
    for(int i=1;i<=n;i++)
    {
        result=left+right;
        left=right;
        right=result;
    }
    return result;
}
int main()
{
    while(true)
    {
        int n;
        cin>>n;
        cout<<fib(n)<<endl;
    }
}

最后时间复杂度为O(n),而且也不需要开新的空间存放计算结果。

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x