斐波那契数
迭代法
class Solution { public: int fib(int n) { if(n <=1 ) return n; int pre0 = 0 , pre1 = 1; int num = n-2; while(num--) { int tmp = pre0 + pre1; pre0 = pre1; pre1 = tmp; } return pre0+pre1; } };
动态规划（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<dp.size();i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };
二刷
class Solution { public: int fib(int n) { if(n <= 1) return n; vector<int> dp(n+1,0); dp[0] = 0; dp[1] = 1; for(int i=2 ; i<=n ; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };
