大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
斐波那契数列的公式（和跳台阶的方式不同）
F(0) = 0;F(1) =1;F(n)=F(n-1)+F(n-2);
方法一：使用递归
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
运行效率：
运行时间：1284ms
占用内存：21560k
方法二：循环方式
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n==1)
return 1;
int n1 = 0;
int n2 = 1;
int total = 0;
for(int i = 2; i<=n;i++)
{
total = n1 + n2;
n1 = n2;
n2 = total;
}
return total;
}
}
运行效率：
运行时间：16ms
占用内存：23036k
方法三：
public class Solution {
public int Fibonacci(int n) {
int f = 0, g = 1;
while(n-->0) {
g += f;
f = g - f;
}
return f;
}
}
运行效率:
运行时间：19ms
占用内存：22848k
