题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
最基础的计算机算法，实现起来，一般情况下有两种选择，递归and迭代
递归版本
public class Solution {
public int Fibonacci(int n) {
if(n <= 1){
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
由于使用有大量的函数调用，深度也比较大，并且很多重复运算，所以时间复杂度比较高
斐波那契数列的每一个数字都是与之前两个相关的，所以，以此为入手点，使用迭代，与简单递归相比省去很多的时间。
public class Solution {
public int Fibonacci(int n) {
if(n <= 1){
return n;
}
int[] a = {0, 1};
int sum = 0;
for(int i = 2; i <= n; i++){
sum = a[0] + a[1];
a[0] = a [1] ;
a[1] = sum;
}
return sum;
}
}
public class Solution {
public int Fibonacci(int n) {
if(n <= 1){
return n;
}
int[] a = {0, 1};
while(n-- >= 2){
a[1] += a[0] ;
a[0] = a[1] - a[0];
}
return a[1];
}
}
上面两种方法都是一样的，第二种方法做了一些优化，减少了一个临时变量sum
省了一点点空间
但是我上面的方法为了较好的理解都是用了数组来实现，如果改成普通的int来存储会更加节省空间。
image.png
