生成斐波那契数列的两种方法

记忆化递归

我们会发现，如果直接使用递归来进行计算斐波那契数列，那会出现很多的重复计算，我们可以把已经计算过的数值进行保存，然后当每次计算的时候先判断是否存在已经计算好的数值。有的话就直接调用，没有的话就进行计算并保存这个值。

#include<iostream>
using namespace std;
//记忆化递归

long long dp[45];

long long fib(int n)
{
    if(n==1||n==0) return 1;
    if(dp[n]) return dp[n];

    dp[n] = fib(n-1) + fib(n-2);
    return dp[n];
}


int main()
{
    int n;
    cin>>n;
    cout<<fib(n)<<endl;
}

动态规划法

#include<iostream>
using namespace std;

long long f[50];

int main()
{
    int n;
    cin>>n;
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=n;i++)
        f[i] = f[i-1]+ f[i-2];
    cout<<f[n]<<endl;
}

综上所述，将小规模局部问题存储在内存之中，在进行大规模运算的时候，就可以直接把这些之前计算好的值拿来直接应用，这就是动态规划法的基本思路。