动态规划——斐波那契数列

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

斐波那契数列

source 代码随想率动态规划

#include<bits/stdc++.h>
using namespace std;
int fib(int n)
{
    if(n<=1) return n;
    vector<int> dp(n+1);
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++) //do not forget the equal
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}
//time complexity o(n) space complexity o(n)
//
//we can see that :we only need to maintain two value which was used to continue
int fib2(int n)
{
    if(n<=1) return n;
    int dp[2];
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++)//do not forget the equal
    {
        int sum=dp[0]+dp[1];
        dp[0]=dp[1];
        dp[1]=sum;
    }
    return dp[1];
}
//time complexity o(n) space complexity o(1)
//
//递归
int fib3(int n)
{
    if(n<2) return n;
    return fib(n-1)+fib(n-2);
}
//time complexity o(2^n) space complexity o(n)


int main()
{
    cout<<fib2(3)<<endl;

    return 0;
}

动态规划——斐波那契数列

推荐阅读