斐波那契数列

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

第一种

最容易想到的方式：

使用递归的方式，自底向上

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

优化思路：

一：使用数组存储

优化，我们使用数组来存，但是效果不明显

public class Solution {
    
    int[] arr = new int[40];
    public int Fibonacci(int n) {
         
        if(n == 0){
            return 0;
        }
        if(n==1){
            return 1;
        }
         
        arr[n]  =  Fibonacci(n-1)+Fibonacci(n-2);
        return arr[n];
        
    }
}

优化思路二：

非递归，使用循环方式，每次存储n-1以及n-的值，值存储需要用到的值，那么就可以进行计算

考虑到每一次只存储n-1以及 n-2个数，所以可以只存储前一次计算的前两个值

public class Solution {
 
    public int Fibonacci(int n) {      
        if(n == 0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        
        int a=0,b=1,c=0;
        //a 代表n-2的值，b 代表n-1的值
        for(int i = 2 ; i<=n ;i++){
            c = a+b;
            a = b;
            b = c;           
        }     
        return c;
        
    }
}