題目描述：
· 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n优构，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。n<=39
解題思路：
思路一：遞歸（時(shí)間復(fù)雜度高）
斐波那契數(shù)列遞歸公式
思路二：循環(huán)
用兩個(gè)變量保存前兩個(gè)數(shù)值损痰，計(jì)算兩個(gè)變量的和并更新變量葡盗，這樣只需計(jì)算一次。
代碼實(shí)現(xiàn)
思路1：遞歸
class Solution {
public:
int Fibonacci(int n) {
if(n<=0)
return 0;
if(n==1)
return 1;
return Fabonacci(n-1)+Fabonacci(n-2);
}
};
思路2：循環(huán)
class Solution {
public:
int Fibonacci(int n) {
int res[2]={0,1};
if(n<2){
return res[n];
}
int fib1,fib2,fib;
fib1=0;
fib2=1;
fib=0;
for(int i=2;i<=n;i++){
fib=fib1+fib2;
fib1=fib2;
fib2=fib;
}
return fib;
}
};
};
