1.題目概述
- 大家都知道斐波那契數(shù)列瓮具，現(xiàn)在要求輸入一個(gè)整數(shù)n院喜，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)场刑。n<=39
2.解題思路
- 斐波那切數(shù)列性質(zhì)
f(1)=0,f(2)=1,f(n)=f(n-1)+f(n-2)
很典型的遞歸思路鳄乏。嗯，這樣想你就上當(dāng)了区丑，關(guān)于斐波那契數(shù)列拧粪，遞歸時(shí)間復(fù)雜度為n!,這樣太高，需要使用迭代進(jìn)行改進(jìn)沧侥。
public class Solution {
public int Fibonacci(int n) {
int item=0;
if (n<=1) return n;
else {
item=Fibonacci(n-1)+Fibonacci(n-2);
return item;
}
}
}
迭代：
public class Solution {
public int Fibonacci(int n) {
int item=0;
int f1=0;
int f2=1;
if (n<=1) return n;
else {
for(int i=2;i<=n;i++){
item=f1+f2;
f1=f2;
f2=item;
}
}
return item;
}
}
