算法训练营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};}
}