剑指 Offer（第2版）面试题 10：斐波那契数列

剑指 Offer（第2版）面试题 10：斐波那契数列

题目来源：21. 斐波那契数列

解法1：递归

代码：

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

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

解法2：动态规划

代码：

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

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

解法3：动态规划 - 空间优化

用 3 个变量就能代替之前的动态规划数组。

代码：

class Solution {
public:int Fibonacci(int n) {int first = 0, second = 1;while(n--){int res = first + second;first = second;second = res;}return first;}
};

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(1)。