在通过递归和记忆化搜索解决斐波那契数列后,我们现在来看看如何通过动态规划计算斐波那契数列。
动态规划
什么是动态规划
对于斐波那契数列,如果使用单纯的递归算法,会导致冗余计算的增长是“爆炸性”的。于是我们用记忆化搜索,新建一个用于存储“已经解决过的子问题”的表以避免冗余计算。
而记忆化存储,其实也算动态规划的一种。动态规划(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),而且也不需要开新的空间存放计算结果。