按照斐波那契额数列的递推公式 f(n)=f(n-1)+f(n-2) 推算即可。
使用递归会造成不必要的重复计算，并且如果要求的值比较大，则可能造成函数调用栈的溢出。所以最好使用循环解决，算法复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int Fibonacci(int n) {
if(n<=0) return 0;
if(n<=2) return 1;
int first=1;
int second=1;
for(int i=3;i<=n;i++){
int third=first+second;
first=second;
second=third;
}
return second;
}
};
|