算法训练营Day47(打家劫舍）

?198.打家劫舍?

198. 打家劫舍 - 力扣（LeetCode）

dp数组：i-1,考虑到i-1的最大数组得到的最大金币

递推公式：

? ? ? ? 抢i： dp[i-2] +nums[i]

? ? ? ? 不抢i：dp[i-1]

? ? ? ? dp[i] = max(dp[i-2] +nums[i],dp[i-1])

初始化：

? ? ? ? index 0:就一个，必须偷

? ? ? ? index 1:偷大的，max（）

遍历顺序：

? ? ? ? 顺序就可以了

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];
        int [] dp = new int[nums.length];
        dp[0] = nums[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??

213. 打家劫舍 II - 力扣（LeetCode）

在1的基础上，分别考虑头尾就可以了

class Solution {
    public int rob(int[] nums) {
        if(nums==null||nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        int [] begin = new int [nums.length-1];
        int [] end = new int [nums.length-1];
        System.arraycopy(nums,0,begin,0,nums.length-1);
        System.arraycopy(nums,1,end,0,nums.length-1);
        return Math.max(rob1(begin),rob1(end));
    }
    public int rob1(int[] nums) {
       
        int [] dp = new int[nums.length];
        dp[0] = nums[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];
    }
}

?337.打家劫舍III

337. 打家劫舍 III - 力扣（LeetCode）

dp数组：

? ? ? ? 每个节点两个，dp[0]表示不偷的最大金额，dp[1]表示偷了的最大金额

/**
 * 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 {
    private ArrayList<Integer> list = new ArrayList<>();
    public int rob(TreeNode root) {
        int[] result = robTree(root);
        return Math.max(result[0],result[1]);  
    }
    private int[] robTree(TreeNode root){
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robTree(root.left);
        int[] right = robTree(root.right);

        //偷这个节点
        int value1 = root.val+left[0]+right[0];
        //不偷这个节点，偷孩子
        int value2 = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{value2,value1};

    }
}