198 打家劫舍

看完题后的思路

看完题后的思路

1. dp【i】：0-i的房间，所能获得的最大金钱数
2. 当偷第i间房子的时候，有偷和不偷两种情况， 不偷，dp【i】=dp【i-1】 偷 dp【i】=dp【i-2】+v【i】
3. 初始换 dp【0】=v【0】 dp【1】=max（v【0】，v【1】）
4. 从左到右遍历

代码

public int rob(int[] nums) {int[] dp = new int[nums.length];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]);}dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;idp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}

213.打家劫舍II

看完题后的思路

对于 0-i，可以先偷 a=【0，i-1】，再头 b=【1，i】
if a =b，说明第一个和最后一个都没有偷，加上两端的一个最大值,这句话不对，如果加上最大值，例如加上最后一个，但是倒数第二个偷了，会出发报警，所以直接返回a,b最大值就行否则，直接返回a，b之间的最大值

class Solution {public int rob(int[] nums) {int[] dp1 = new int[nums.length];int[] dp2 = new int[nums.length];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]);}dp1[0]=nums[0];dp1[1]=Math.max(nums[0],nums[1]);dp2[1]=nums[1];dp2[2]=Math.max(nums[1],nums[2]);for(int i=2;idp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i]);}for(int i=3;idp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);}boolean b = dp1[nums.length - 2] == dp2[nums.length - 1];// if (nums.length>3&&b){//    return dp2[nums.length - 1]+Math.max(nums[0],nums[nums.length-1]);// }return Math.max(dp1[nums.length - 2] , dp2[nums.length - 1]);}
}

337.打家劫舍III

看完题目后的思路

本题是树形dp

1. dp【0】 不选则本节点 ，dp【1】=选择本节点
2. 递归终止条件
   if（root==null）{return {0,0}}
3. 递归
   left=f（root.left）;
   right=f(root.right)
   选择当前节点时： left【1】+right【1】+root.val
   不选择当前节点时： max（left【0】，left【1】）+max（right【0】，right【1】）
   将上面两个值在数组中返回

代码

        public int rob(TreeNode root) {int[] ints = robDG(root);return Math.max(ints[0],ints[1]);}public int[] robDG(TreeNode root) {if (root==null){return new int[]{0,0}; }int[] left = robDG(root.left);int[] right = robDG(root.right);return new int[]{Math.max(left[0],left[1])+Math.max(right[0],right[1]),left[0]+right[0]+root.val};}