在打家劫舍問題中丹喻，不一定需要dp數(shù)組贱鄙，需要記錄狀態(tài)值，要脫離背包思維潮罪，已經(jīng)不是背包問題了康谆，沒有物品和背包容量的概念了

LeetCode 198

題目連接：打家劫舍I
對于這道題來說，其實并不需要dp數(shù)組嫉到，只需要記錄前兩位的狀態(tài)即可沃暗，當前位置的狀態(tài)僅僅與前兩位的狀態(tài)有關(guān)

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

這道題實現(xiàn)了只用兩個狀態(tài)遞推的方式，核心代碼為

/*如果寫為
first = second; 
second = cur; 
cur = Math.max(first + nums[i], second);
不利于第一個節(jié)點的處理何恶，會出現(xiàn)邊界問題孽锥，還需要進一步分情況處理
*/
second = cur; 
cur = Math.max(first + nums[i], second);
first = second;

這樣的賦值方式，有利于處理第一個節(jié)點（邊界問題）

而這道題的解題思路也是對的细层，就是分開考慮會成環(huán)的頭尾節(jié)點惜辑，分別計算沒有尾節(jié)點的序列最大值和沒有頭節(jié)點的序列最大值，并選出更大的那一個作為結(jié)果

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盛撑，問題一開始嘗試使用層序遍歷，認為為了最大化捧搞，選了一層的某一個元素抵卫，應(yīng)該把整層都選上狮荔，失敗用例如下：

失敗案例.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;
    }
}