斐波那契数列:递归和记忆化搜索

通过斐波那契数列了解递归与记忆化搜索

在学习动态规划前,首先得对递归有一定的了解。

斐波那契数列

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项和的结果存到数组里,要的时候就从数组里取。只不过记忆化搜索是相当于递归来说的。

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