198. 打家劫舍

https://leetcode.cn/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
image.png

确定dp数组（dp table）以及下标的含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

确定dp公式

决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房）
image.png
image.png
然后dp[i]取最大值，即dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);

初始化

有递推公式我们需要初始化dp[0] dp[1]从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = Math.max(nums[0], nums[1]);

遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if (nums == null || nums.length == 0) return 0;
  4.         if (nums.length == 1) return nums[0];
  5.         //dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
  6.         int[] dp = new int[nums.length];
  7.         //初始化条件，由递推公式和dp含义推
  8.         dp[0] = nums[0];
  9.         dp[1] = Math.max(nums[0],nums[1]);
  10.         //遍从前往后遍历顺序
  11.         for(int i = 2; i < nums.length;i++){
  12.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  13.         }
  14.         return dp[nums.length - 1];
  15.     }
  16. }

213. 打家劫舍 II

image.png
环形即需要考虑了我们的首部和尾部因为相连，所以只能选择一个其余和上面一个一样

class Solution {
    public int rob(int[] nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    //情况1 取首部不取尾部
    int res1 = robRange(nums,0,nums.length - 2);
    //情况1 取尾部不取首部
    int res2 = robRange(nums,1,nums.length - 1);
    return Math.max(res1,res2);
    }
    //下面和上一题都是一致的思路

    int robRange(int[] nums,int start,int end){
        if(start == end) return nums[start];
        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

image.png
https://leetcode.cn/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/

/**
 * 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 {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        if (root.left != null) {
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo));
        memo.put(root, res);
        return res;
    }
}