leetcode - 自顶向下解决 198.打家劫舍 问题

先确定递归结构
对于[1,2,3,1]的房子
我们可以有以下几种偷法
一： 1 +[3,1]
二：2+[1]
三：3
四：1

对于n个房子可以
一：1+[3，4，。。。，n]
二：2+【4，5，。。。，n】
三：3+【5，6，。。。。，n】
。
。
。
N：n

这样递归结构就出来了 res 随便赋一个初始值0
这是tryRob的函数的定义
也就是我们要递归的函数
int tryRob(int[] nums, int index)
递归的结束条件就是
if(index >= nums.length){ return 0; }
递归的方程：当前的值 + 剩余的房子总值（从下下个房子开始偷）

for(int i = index;i < nums.length;i++){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }

这样 我们完成了基本的递归结构 但是我们发现现在会有很多的重复计算，这就需要一个记忆化的数组 来存储算过的值
我们叫 memo[] 给他赋初值为-1 memo[i] 代表抢劫nums[i...n)所获得的最大收益

memo = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            memo[i] = -1;
        }

然后在哪里判断呢？我们在每次进入递归函数的时候就要进行判断

private int tryRob(int[] nums, int index){
        if(index >= nums.length){
            return 0;
        }
        if(memo[index] != -1){
            return memo[index];
        }

总体的代码如下：

public class Rob_02 {
    private int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            memo[i] = -1;
        }
        return tryRob(nums, 0);
    }
    private int tryRob(int[] nums, int index){
        if(index >= nums.length){
            return 0;
        }
        if(memo[index] != -1){
            return memo[index];
        }
        int res = 0;
        for(int i = index;i < nums.length;i++){
            res = Math.max(res, nums[i] + tryRob(nums, i+2));
        }
        memo[index] = res;
        return res;
    }
}