题解 | #斐波那契数列#

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

方法1 递归法
最常见的递归法，对于递归算法的时间复杂度，我们有如下计算方法：
递归的次数 * 每次递归中的操作次数
在下列递归代码中，每一次递归都会调用两次递归，可以把递归抽象成一棵二叉树，这样二叉树的节点数就是一共的操作次数， 二叉树一共有n层，共有2^n个节点 ，故时间复杂度为O(2^n)。
空间复杂度：递归栈的空间

public class Solution {
    public int Fibonacci(int n) {
        if(n<0){
            return -1;
        }
        if(n==0 || n==1){
            return n;
        }
        else{
            return Fibonacci(n-2) + Fibonacci(n-1);
        }
    }
}

方法2 数组法
由于递归会有大量重复计算，造成效率的低下，我们直接用数组保存每次计算结果即可
时间复杂度 O(n)
空间复杂度 O(n)

public class Solution {
    public int Fibonacci(int n) {
        int[] array = new int[40];
        array[0] = 0;
        array[1] = 1;
        for(int i=2; i<array.length; i++){
            array[i] = array[i-1] + array[i-2];
        }
        return array[n];
    }
}

方法3 优化空间
我们发现在方法2中数组中前面的元素对后续计算起不到作用，所以我们直接用两个变量保存值即可。

public class Solution {
    public int Fibonacci(int n) {
        int i0 = 0;
        int i1 = 1;
        int result = 1;
        if(n==0){
            return 0;
        }
        for(int i=1; i<n; i++){
            result = i0 + i1;
            i0 = i1;
            i1 = result;
        }
        return result;
    }
}