198.打家劫舍（简单）

题目：192.打家劫舍
两种情况：偷或是不偷
dp[i]，第i户，对应金额是nums[i-1]
不偷：dp[i]=dp[i-1]
偷：dp[i]=dp[i-2]+nums[i-1]

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.       int n=nums.length;
  4.       int[] dp=new int[n+1];
  5.       dp[1]=nums[0];
  6.       for(int i=2;i<=n;i++){
  7.         dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
  8.       }
  9.       return dp[n];
  10.     }
  11. }

213.打家劫舍II（中等）

题目：213. 打家劫舍 II
这个地方所有的房屋都 围成一圈

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.       int n=nums.length;
  4.       if(n==1) return nums[0];
  5.       int[] dp=new int[n];
  6.       //偷第一户,nums[0]~nums[n-2]
  7.       dp[1]=nums[0];
  8.       for(int i=2;i<n;i++){
  9.         dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
  10.       }
  11.       int res=dp[n-1];
  12.       //不偷第一户,nums[1]~nums[n-1]
  13.       dp[1]=nums[1];
  14.       for(int i=2;i<n;i++){
  15.         dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
  16.       }
  17.       res=Math.max(res,dp[n-1]);
  18.       return res;
  19.     }
  20. }

337.打家劫舍III（中等）

题目：337.打家劫舍III
树状偷
image.png
ans[0]不偷当前节点
ans[1]偷当前节点

  1. class Solution {
  2.     public int rob(TreeNode root) {
  3.         int[] ans=dfs(root);
  4.         return Math.max(ans[0],ans[1]);
  5.     }
  7.     public int[] dfs(TreeNode root){
  8.         if(root==null){
  9.             return new int[]{0,0};
  10.         }
  11.         int[] left=dfs(root.left);
  12.         int[] right=dfs(root.right);
  14.         int[] ans=new int[2];
  15.         ans[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]); //注意此处
  16.         ans[1]=root.val+left[0]+right[0];
  18.         return ans;
  19.     }
  20. }