在打家劫舍问题中，不一定需要dp数组，需要记录状态值，要脱离背包思维，已经不是背包问题了，没有物品和背包容量的概念了

LeetCode 198

题目连接：打家劫舍I
对于这道题来说，其实并不需要dp数组，只需要记录前两位的状态即可，当前位置的状态仅仅与前两位的状态有关

class Solution {
    public int rob(int[] nums) {
        //dp[j]为偷到第j家最多能偷多少
        int[] dp = new int[nums.length+1];

        //初始化
        dp[0] = 0;
        dp[1] = nums[0];
        for(int j=2; j<=nums.length; j++){
            dp[j] = Math.max(dp[j-1], dp[j-2]+nums[j-1]);
        }
        return dp[nums.length];
    }
}

LeetCode 213

题目连接：打家劫舍II

这道题实现了只用两个状态递推的方式，核心代码为

/*如果写为
first = second; 
second = cur; 
cur = Math.max(first + nums[i], second);
不利于第一个节点的处理，会出现边界问题，还需要进一步分情况处理
*/
second = cur; 
cur = Math.max(first + nums[i], second);
first = second;

这样的赋值方式，有利于处理第一个节点（边界问题）

而这道题的解题思路也是对的，就是分开考虑会成环的头尾节点，分别计算没有尾节点的序列最大值和没有头节点的序列最大值，并选出更大的那一个作为结果

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];

        //去除尾元素，求得最大值
        int first = 0;
        int second = 0;
        int cur = 0;
        for(int i=0; i<nums.length-1; i++){
            second = cur;
            cur = Math.max(first + nums[i], second);
            first = second;
        }

        //去除头元素
        first = 0;
        second = 0;
        int cur_2 = 0;
        for(int i=1; i<nums.length; i++){
            second = cur_2;
            cur_2 = Math.max(first + nums[i], second);
            first = second;
        }
        return Math.max(cur, cur_2);
    }
}

LeetCode 337

题目连接：打家劫舍III
树形dp，问题一开始尝试使用层序遍历，认为为了最大化，选了一层的某一个元素，应该把整层都选上，失败用例如下：

失败案例.png

class Solution {
    public int rob(TreeNode root) {
        int [] result = treeDp(root);
        return Math.max(result[0], result[1]);
        
    }
    public int[] treeDp(TreeNode cur){
        int[] result = new int[2];
        if(cur==null) return result;

        int[] left = treeDp(cur.left);
        int[] right = treeDp(cur.right);

        //不选cur
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //选cur
        result[1] = left[0] + right[0] + cur.val;
        return result;
    }
}