打家劫舍

198. 打家劫舍

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

213. 打家劫舍 II

if(nums.length==1){
  return nums[0];
}else if(nums.length==2){
  return Math.max(nums[0],nums[1]);
}
int caseone=robcase(nums,0,nums.length-2);
int casetwo=robcase(nums,1,nums.length-1);
return Math.max(caseone,casetwo);
}
private int robcase(int[]nums,int start,int end){
  if(end-start==1){
    return Math.max(nums[start],nums[end]);
  }
  int[]dp=new int[nums.length];
  dp[start]=nums[start];
  dp[start+1]=Math.max(nums[start],nums[start+1]);
  for(int i=start+2;i<=end;i++){
    dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
  }
return dp[end];

337. 打家劫舍 III

int[] robcase = robcase(root);
return Math.max(robcase[0],robcase[1]);
}
private int[] robcase(TreeNode root){
  int[]dp=new int[2];
  if(root==null){
    return dp;
  }
  int[] left = robcase(root.left);
  int[] right = robcase(root.right);
  //偷儿子节点
  dp[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
  dp[1]=left[0]+right[0]+root.val;
return dp;