题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
思路：1、递归 ； 2、采用数组存历史数据； 3、不用数组存储
1、递归（推荐）来自：http://blog.csdn.net/sinat_34967445/article/details/76752882
int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
2、采用数组存历史数据
public class Solution {
public static int Fibonacci(int n) {
int[] arr=new int[40];
arr[0]=0;
arr[1]=1;
for(int i=2;i<=n;i++){
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n];
}
}
3、不用数组存储
public class Solution {
public static int Fibonacci(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
int f0=0;
int f1=1;
int f2=0;
for(int i=2;i<=n;i++){
f2=f1+f0;
f0=f1;
f1=f2;
}
return f2;
}
}
