【动态规划算法题记录】 509. 斐波那契数

递归法

看到题目的第一眼，直接递归！完事

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

动态规划

1. 确定dp数组以及下标的含义
   dp数组这里就是斐波那契数列，dp[i]即第i个数的斐波那契值。
2. 确定递推公式
   dp[i] = dp[i-1] + dp[i-2]
3. dp数组初始化
   dp[0] = 0;
dp[1] = 1;
4. 确定遍历顺序
   因为dp[i]是由它的前两个数决定，所以我们只能从前往后去遍历。

class Solution {
public:
    int fib(int n) {
        if(n < 2) 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];
    }
};