在学习动态规划前,首先得对递归有一定的了解。
斐波那契数列
F(n)=F(n – 1)+F(n – 2) (n>2)
斐波那契数列的前两项为1。从第三项开始,每一项都等于它的前两项的和。
- F(1)=1 F(2)=1
- F(3)=F(2)+F(1)=2
- F(4)=F(3)+F(2)=3
- …
- F(n)=F(n-1)+F(n-2)
有时候还会出现F(0)的情况。不过F(0)=0,还是比较好处理的。
递归计算斐波那契数列
C++实现
如果用C++求斐波那契,代码如下
#include<iostream>
using namespace std;
int fib(int n)
{
if(n<=1)
{
return n;
}
return fib(n-2)+fib(n-1);
}
int main()
{
while(true)
{
int n;
cin>>n;
cout<<fib(n)<<endl;
}
}
其中,递归的过程类似于一个二叉树。比如求F(4)时
- F(5)不满足n<2,返回fib(4)+fib(3)
- F(4)和F(3)都不满足条件,前者继续计算F(3)+F(2),后者计算F(2)+F(1)
- F(3)+F(2)还是不满足条件,继续计算F(2)+F(1)
可以看到,F(2)+F(1)被计算了两次。这里引用下leetcode题解中的图片。

那么这里就是我们优化的出发点了。我们可以把计算过的结果储存起来,如果已经计算过了该项的F(n),那么下次计算的时候直接用就好了。
这种方法又被叫做“记忆化搜索”。因为每次在运算前它会先根据“记忆”去搜索之前是否有计算过该值,计算过则直接返回。
#include<iostream>
#include<vector>
using namespace std;
vector<int>memo;
int fib(int n)
{
if(n<=2)
{
return 1;
}
if(memo[n]!=0)
{
return memo[n];
}
memo[n]=fib(n-2)+fib(n-1);
return memo[n];
}
int main()
{
while(true)
{
int n;
cin>>n;
memo.resize(n);
cout<<fib(n)<<endl;
}
}
我个人感觉有点像前缀和。前缀和也是把前n项和的结果存到数组里,要的时候就从数组里取。只不过记忆化搜索是相当于递归来说的。