先确定递归结构
对于[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;
    }
}