代码随想录算法训练营Day39|198.打家劫舍 123

198.打家劫舍

        做完背包问题，打家劫舍感觉容易好多。主要理解每一家都又两个状态偷和不偷即可。好像回到了最初的爬楼梯。

       dp[i]: 偷到第i家时候的最大值

        递推：            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);

        偷第i家和不偷第i家的最大值。

        初始化：头两家初始化就好了。注意可能数组只有一个元素，导致越界。

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if(nums.length == 1){
            return dp[0];
        }
        dp[1] = Math.max(nums[0],nums[1]);

        for(int i = 2; i<nums.length; i++){
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }

        return dp[nums.length -1];
     }
}

213.打家劫舍II

         思路：分成两部分，一部分是取头不取尾，一个是取尾不取头。然后整体思路和上一题一样，注意下边界即可。

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

    public int maxValue(int[] nums, int left, int right){
        int[] dp = new int [right-left + 1];
        dp[0] = nums[left];
        if(right-left + 1  == 1){
            return dp[0];
        }
        dp[1] = Math.max(nums[left+1],nums[left]);
        for(int i = 2; i< dp.length;i++){
            dp[i] = Math.max(dp[i-2] +nums[left + i], dp[i-1]);
        }
        return dp[right - left];
    }
}

337.打家劫舍 III

         看了题解，但是为数不多的一次都没报错。

        每个节点都有偷和不偷的两种状态，用一个数组存起来。主要是递归的框架，还有偷和不偷的两个公式，还是比较好理解的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] resdp = fun(root);
        int res = Math.max(resdp[0],resdp[1]);
        return res; 
    }

    public int[] fun(TreeNode cur){
        if(cur == null) return new int[]{0,0};
        int[] left = fun(cur.left);
        int[] right = fun(cur.right);
        int steal = cur.val + left[0] + right[0];
        int notSteal = Math.max(left[1],left[0]) + Math.max(right[1],right[0]);
        return new int[]{notSteal,steal}; 
    }
}