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; } };