思路：
题目的主要信息：
- 斐波那契数列每项的公式为:
，从0开始，
，
- 求出斐波那契数列的第n项
- n最大不超过39，结果不会超出int的范围，不用考虑
long long
方法一：递归
具体做法：
根据公式，每次返回，结束递归的点就是1或者0
class Solution {
public:
int Fibonacci(int n) {
if (n <= 1) //从0开始，第0项是0，第一项是1
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2); //根据公式递归调用函数
return 0;
}
};复杂度分析：
- 时间复杂度：
，每个递归会调用两个递归，因此呈现2的指数增长
- 空间复杂度：
, 递归栈的最大深度
方法二：递归优化（记忆化递归）
具体做法：
在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储f(0)至f(n)的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
class Solution {
public:
int dp[40] = {0}; //记忆每次已有的结果
int Fibonacci(int n) {
if (n <= 1){//从0开始，第0项是0，第一项是1
dp[n] = n;
return n;
}
else{
int a, b;
//若是数组中记录了值，直接用省去递归
if(dp[n - 1] == 0)
a = Fibonacci(n - 1);
else
a = dp[n - 1];
if(dp[n - 2] == 0)
b = Fibonacci(n - 2);
else
b = dp[n - 2];
return a + b;
}
return 0;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
方法三：动态规划
具体做法：
创建一个n+1大小的辅助数组dp，初始化第0位为0，第1位为1，然后根据公式依次往后相加即可得到后面的值，数组最后的下标n即为所求。
class Solution {
public:
int Fibonacci(int n) {
if (n <= 1)
return n;
vector<int> dp(n + 1);
dp[0] = 0; //从0开始，第0项是0，第一项是1
dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2]; //公式相加
return dp[n];
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
方法四：动态规划空间优化
具体做法：
动态规划申请了一个数组，但是我们可以发现其实每次需要的只是i-1和i-2的值，我们可以用两个变量保存该值，每次更新即可。
class Solution {
public:
int Fibonacci(int n) {
if (n <= 1) //从0开始，第0项是0，第一项是1
return n;
int i_2 = 0; //分别记录i-1与i-2的值
int i_1 = 1;
int res = 0;
for (int i = 2; i <= n; i++){
res = i_1 + i_2;
i_2 = i_1; //更新i-1与i-2
i_1 = res;
}
return res;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
，未申请空间
京公网安备 11010502036488号