/*class Solution {
    public int fib(int n) {
        if(n == 1 || n ==2)
        return 1;
        else
        return fib(n-1) + fib(n-2);
    }
}
这种写法会导致直接爆掉
*/

class Solution {
    public int fib(int N) {
        int[] memo = new int[N + 1];        //memo就是备忘录的意思
        return helper(memo, N);             //要求helper返回数组 memo 第 n+1 个值 
    }
    int helper(int[] memo, int n) {         //其实helper就是尾递归
        if (n == 0 || n == 1) return n;     //初始化条件
        if (memo[n] != 0) return memo[n];   //如果memo已经有值了，则返回，递归的出口
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);      //★★★ 通过这一步实习尾递归
        return memo[n];                     //递归后的返回
    }
}

//动态规划
class Solution {
    public int fib(int n) {
        if(n == 0)
        return 0;                    //为什么不对 n==0 这个情况进行判断就会报错呢？
        int[] dp = new int[n+1];     

        dp[0] = 0;                  //初始化条件
        dp[1] = 1;

        for(int i=2; i<=n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
/*
输入0，显示下标越界了，，哦哦，不对，不是下标越界，是数组的长度不能是 1 .
但是输入1却直接输出了
*/

//优化后的动态规划
class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1)
        return n;
        int dp_i = 0;
        int dp_i_1 = 0;
        int dp_i_2 = 1;

        for(int i=2; i<=n; ++i){
            dp_i = dp_i_1 + dp_i_2;
            dp_i_1 = dp_i_2;            
            dp_i_2 = dp_i;
        }
        return dp_i_2;
    }
}