1.题目概述
- 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
2.解题思路
- 斐波那切数列性质
f(1)=0,f(2)=1,f(n)=f(n-1)+f(n-2)
很典型的递归思路。嗯，这样想你就上当了，关于斐波那契数列，递归时间复杂度为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;
}
}
