剑指 Offer（第2版）面试题 10：斐波那契数列
剑指 Offer（第2版）面试题 10：斐波那契数列
- 剑指 Offer（第2版）面试题 10：斐波那契数列
- 解法1：递归
- 解法2：动态规划
- 解法3：动态规划 - 空间优化
剑指 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)。