509 斐波那契数
https://leetcode.cn/problems/fibonacci-number/description/
递归
class Solution {
public:
int fib(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
};
- 时间复杂度:\(O(2^n)\)
- 空间复杂度:\(O(n)\),算上了编程语言中实现递归的系统栈所占空间
动态规划
class Solution {
public:
int fib(int n) {
if(n <= 1)
return n;
vector<int> num(n + 1);
num[0] = 0;
num[1] = 1;
for(int i = 2; i <= n; i++){
num[i] = num[i - 1] + num[i - 2];
}
return num[n];
}
};
- 时间复杂度:\(O(n)\)
- 空间复杂度:\(O(1)\)
动态规划优化
class Solution {
public:
int fib(int n) {
if(n <= 1)
return n;
int a = 0;
int b = 1;
int c;
for(int i = 2; i <= n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
};
- 时间复杂度:\(O(n)\)
- 空间复杂度:\(O(1)\)