【动态规划算法题记录】 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];}
};