不说话

方法1：递归

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);
    }
}

方法2：优化递归，消除重复计算

public class Solution {
    //优化递归，记忆化过程，防止重复计算
    int[] arr = new int[40];
    public int Fibonacci(int n) {
        if(n==0||n==1) {
            return n;
        }
        int result = arr[n];
        if(result==0){
            result = Fibonacci(n-1)+Fibonacci(n-2);
            arr[n] = result;
        }
        return result;
    }
}

方法3：动态规划

public class Solution {
    //动态规划
    public int Fibonacci(int n) {
        if(n==0||n==1) {
            return n;
        }
        int result = 0;
        int result1 = 1;
        int result2 = 0;
        int i=2;
        while(i<=n){
            result = result1+result2;
            if(result1>=result2){
                result2 = result;
            }else{
                result1 = result;
            }
            i++;
        }
        return result;
    }
}