（java版剑指offer）JZ10 斐波那契数列

//方法一：递归
//时间复杂度:2^n
//空间复杂度：n
public class Solution {
    public int Fibonacci(int n) {
        if(n<=1){
            return n;    //n为1，返回1；n为0，返回0
        }
        return Fibonacci(n-1) + Fibonacci(n-2);    //递归
        //f(2)=f(1)+f(0)=1+0
        //f(3)=f(2)+f(1)=1+1 = 2
    }
}

//方法二：数组存储法
//时间复杂度: n
//空间复杂度：n
public class Solution {
    public int Fibonacci(int n) {
        int[] ans = new int[40];    //新建一个数组
        ans[0] = 0;
        ans[1] = 1;
        //遍历存储1-40对应的斐波拉契数据于数组中
        for(int i=2;i<=n;i++){
            ans[i] = ans[i-1] + ans[i-2];    //每个数组下标位置存放有对应的斐波拉契数据
        }
        return ans[n];    //通过数组下标即可寻得对应的斐波拉契数据，有些费空间
    }
}

//方法三：相邻三个数存储法
//时间复杂度: n
//空间复杂度：1
public class Solution {
    public int Fibonacci(int n) {    
        if(n <= 1){
            return n;
        }
        
        //只存储相邻三个数
        int left_1 = 0;
        int left_2 = 1;
        int last = 0;
        
        for(int i=2; i<=n; i++){
            last = left_1 +left_2;
            left_1 = left_2;
            left_2 = last;
        }
        
        return last;
    }
}

//方法四：只存储相邻两个元素
//时间复杂度: n
//空间复杂度：1
public class Solution {
    public int Fibonacci(int n) {    
        if(n <= 1){
            return n;
        }
        
        //只存储相邻两个数
        int left = 0;
        int last = 1;
        for(int i=2; i<=n; i++){
            last = left + last;    //末尾元素
            left = last - left;    //相邻左边的元素
        }
        return last;
    }
}