题目描述
输入一个整数$ n $,求斐波那契数列的第$ n $项。
假定从$ 0 $开始,第$ 0 $项为$ 0$。$(n≤39)$
样例
n=5
返回 5
算法1
(递推) $O(n+1)$
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
int a,b=1,c;
while(n--) {
c=a+b;
a=b;
b=c;
}
b=a;
return b;
}
};
算法2
(递归) $O((n-1)*2)$
小心爆栈!
C++ 代码
class Solution {
public:
int Fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
};
算法3
(递归+记忆化) $O(n)$
我们发现递归中重复递归了许许多多的斐波那契,所以记忆化就隆重登场了!
C++ 代码
class Solution {
public:
int a[40] = {0};
int Fibonacci(int n) {
if (a[n])
return a[n];
if (n == 0)
return a[n] = 0;
if (n == 1)
return a[n] = 1;
return a[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
}
};