记忆化搜索系列一＞“简单题？“斐波那契数

class Solution {
    int[] memo;//<下标表示第几个斐波那契数，对应的斐波那契数>

    public int fib(int n) {
        memo = new int[31];
        //初始化让元素不包括，原数据的任何数
        Arrays.fill(memo,-1);

        return dfs(n);
    }

    private int dfs(int n){

        //每次进入递归的时候，检查一下备忘录是否已经存在结果，如果存在直接返回
        if(memo[n] != -1){
            return memo[n];
        }

        if(n == 1 || n == 0){
            memo[n] = n; //递归返回之前，把每次的返回结果放到备忘录
            return n;
        }

        //递归返回之前，把每次的返回结果放到备忘录
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
}

 //动态规划
    public int fib(int n) {
        int[] dp = new int[31];
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }