题目描述:斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

    F(0) = 0，F(1) = 1
    F(n) = F(n - 1) + F(n - 2)，其中 n > 1
    给你 n ，请计算 F(n) 。

题目链接:https://leetcode-cn.com/problems/fibonacci-number/

动态规划五部曲:

1. 确定dp数组以及下标的含义:dp[i]的定义为:第i个数的斐波那契值是dp[i];
2. 确定状态转移方程: dp[i] = dp[i-1] + dp[i-2];
3. dp数组如何初始化: dp[0] = 0;dp[1]=1;
4. 确定遍历顺序: 从状态转移方程 dp[i] = dp[i-1] + dp[i-2]中可以看出,dp[i] 是依赖dp[i-1]和dp[i-2]的,那么遍历的顺序一定是从前往后遍历的.
5. 举例推导dp数组: 按照状态转移方程推导

代码实现:

class Solution {
public:
    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++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

拓展:其它两种解法代码实现:

1.只需要维护两个数值,不需要记录整个序列(不需要额外数组保存过程序列).

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        int first = 0;
        int second = 1;
        int third;
        for(int i = 2;i <= n;i++){
            third = first+second;
            first = second;
            second = third;
        }
        return third;
    }
};

2.递归解法

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        else
            return fib(n-1)+fib(n-2);
    }
};