509.斐波那契数.cpp

动态规划 递归

思路：动态规划的第一题，应当建立解题意识。

动归五部曲：
1：确定dp数组及下标的含义。dp[i]：斐波那契数列的第i个数。
2：确定递推公式。注意是“递推”不是“递归”，此题题干已给出，dp[i]=dp[i-1]+dp[i-2]。
3：初始化dp数组。dp[0]=0、dp[1]=1，这点容易遗忘，需要初始化最前面的，dp[i]毕竟从2开始遍历for()，
前面的dp[1]、dp[0]，需要有值才行。
4：确定遍历顺序。从递推公式dp[i]=dp[i-1]+dp[i-2]可得，遍历顺序是从前往后，即0、1、2、3...n。
5：举例推导dp数组。按题干公式可得，n=10时，序列为0 1 1 2 3 5 8 13 21 34 55。然后用写出的代码运行一遍，
如果不对就在for()里打印出来，cout<<dp[i]<<endl，然后再排查错误原因。

注：for()循环其实i在累加，循环体里也是i在进行递推公式，“一直让i(比如从2开始)累加到n，则dp[]数组从0~n的值就都有了”。

1：虽此题不会出现，但此处可以预防空指针。
2：此处是i<=n，因为i可以到n。

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n; // wyh 1
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) { // wyh 2
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};