动态规划：打家劫舍 II

参考资料：代码随想录

打家劫舍的解法和背包问题是两种不同的解题思路。

但同样是依赖于前面的状态推导。

打家劫舍2的关键思路在于对不同情况的分析。

考虑首节点，不考虑尾结点。

考虑尾结点，不考虑首节点。

从这两个里面选取最大值

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length > 2){
            return Math.max(rob(nums,0,nums.length-2),rob(nums,1,nums.length-1));
        }else {
            return Math.max(nums[0],nums[1]);
        }
        
    }

    private int rob(int[] nums,int startIndex,int endIndex){
        //1.确定dp数组含义
        //int[] dp = new intp[nums.length];
        //2.初始化dp数组
        int x = nums[startIndex];
        int y = Math.max(nums[startIndex],nums[startIndex+1]);
        int z = 0;
        //3.确定遍历顺序
        for(int i = startIndex+2;i <= endIndex;i++){
            z = Math.max(x+nums[i],y);
            x = y;
            y = z;
        }
        return y;
    }
}