入门动态规划题——斐波那契数列（力扣509题）

1.递归方法

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

2.动态规划方法

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

3.迭代法

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