509. 斐波那契数

  1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

  1. 确定递推公式

状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  1. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：
dp[0] = 0; dp[1] = 1;

  1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55

一、dp

  1. class Solution {
  2. public:
  3.     int fib(int n) {
  4.         if(n<2)return n;
  5.         int dp[n+1];
  6.         dp[0]=0,dp[1]=1;
  7.         for(int i =2;i<=n;i++)
  8.         {
  9.             dp[i] = dp[i-1]+dp[i-2];
  10.         }
  11.         return dp[n];
  12.     }
  13. };

二、滚动数组

a,b代表dp[0],dp[1]，c代表下一状态

class Solution {
public:
    int fib(int n) {
        if(n<2)return n;
        int a=0,b=1,c=0;
        for(int i =2;i<=n;i++)
        {
            c = a+b;
            a =b;
            b =c;
        }
        return c;
    }
};