剑指offer----斐波那契数列

题目：大家都知道斐波那契数列，现在要求输入一个整数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