打家劫舍

  1. 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
  3. 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
  6. 示例 1：
  8. 输入：[1,2,3,1]
  9. 输出：4
  10. 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  11.      偷窃到的最高金额 = 1 + 3 = 4 。
  12. 示例 2：
  14. 输入：[2,7,9,3,1]
  15. 输出：12
  16. 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
  17.      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
  20. 提示：
  22. 1 <= nums.length <= 100
  23. 0 <= nums[i] <= 400

方法1:暴力递归

  1. public int rob(int[] nums) {
  2.     return helper(nums, nums.length - 1);
  3. }
  5. //偷了或没偷第i和房间，带来的收益
  6. public int helper(int[] nums, int i) {
  7.     if (i < 0) return 0;
  8.       //偷了第i个房间，则考虑第i-2个房间
  9.     int steal = nums[i] + helper(nums, i - 2);
  10.       //没偷第i个房间，则考虑第i-1个房间
  11.     int non_steal = helper(nums, i - 1);
  12.       //返回偷或者没偷带来的收益
  13.     return Math.max(steal, non_steal);
  14. }

方法2:自顶向下记忆化递归(Top-down)

从前往后跳

  1. Integer[] memo;
  3. public int rob(int[] nums) {
  4.     memo = new Integer[nums.length];
  5.     return helper(nums, 0);
  6. }
  8. /**
  10.  * @param nums
  11.  * @param i    表示当前的房间号
  12.  * @return
  13.    */
  14.    public int helper(int[] nums, int i) {
  15.     //因为是从前往后偷，到达最后一个房间时，退出
  16.    if (i >= nums.length) return 0;
  17.    if (memo[i] != null) return memo[i];
  18.    int steal = nums[i] + helper(nums, i + 2);
  19.    int non_steal = helper(nums, i + 1);
  20.    return memo[i] = Math.max(steal, non_steal);
  21.    }

从后往前跳

  1. Integer[] memo;
  3. public int rob(int[] nums) {
  4.     memo = new Integer[nums.length];
  5.     return helper(nums, nums.length - 1);
  6. }
  8. public int helper(int[] nums, int i) {
  9.     if (i < 0) return 0;
  10.     if (memo[i] != null) return memo[i];
  11.     int steal = nums[i] + helper(nums, i - 2);
  12.     int non_steal = helper(nums, i - 1);
  13.     return memo[i] = Math.max(steal, non_steal);
  14. }

方法3:自底向上填表DP(Bottom-up)

image-20220305200741336.png

定义状态

  • 定义f[n][2]
  • f[i][0] 表示在第i间房子的时候，没偷，所获得的累计金额(房间索引从0开始)
  • f[i][1] 表示在第i间房子的时候，偷了，所获得的累计金额

转移方程

  • f[i][0]与前一个房间的结果有关系，f[i][0]表示当前房间没偷，所以前一个房间是可以偷的，这是符合条件「如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警」即f[i-1][1],如果前一个房间没偷呢？这也是可以的，也就是说当前房间和前一个房间都没有偷，即f[i-1][0]，取这两个值中的最大值，即f[i][0]=max{f[i-1][1],f[i-1][0]}
  • f[i][1]与前一个房间的结果有关系，f[i][1]表示当前房间偷了，要符合条件「如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警」的话，需要前一个房间，一定是没有偷过的，即f[i-1][0]，再加上当前房间所获得的价值，即f[i][1]=f[i-1][0]+nums[i]

初始化

  • 第一间房间没有偷的时候，没有产生金额f[0][0]=0
  • 第一间房间偷了的时候，产生了金额，即第一间房间的钱f[0][1]=nums[0]
  1.      public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             int[][] f = new int[n][2];//0表示今天没偷 1表示偷了
  4.             f[0][0] = 0;
  5.             f[0][1] = nums[0];
  6.             for (int i = 1; i < n; i++) {
  7.                 f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
  8.                 f[i][1] = f[i - 1][0] + nums[i];
  9.             }
  10.             return Math.max(f[n - 1][0], f[n - 1][1]);
  11.         }
  • 也可以将f[n][2]设置成f[n+1][2],计算房间产生的收益的时候，计算是nums[i-1],代码如下：
  1.         public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             int[][] f = new int[n + 1][2];
  4.             for (int i = 1; i <= n; i++) {
  5.                 f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
  6.                 f[i][1] = f[i - 1][0] + nums[i - 1];
  7.             }
  8.             return Math.max(f[n][0], f[n][1]);
  9.         }
  • 进而可以考虑移除掉f[n][2]中的第二维，定义f[n+1],其中f[i]表示偷第i间房间时，产生的前i个房间即[0,i)房间，产生的总金额
    • 初始化时，f[0]=0,因为往前多放了一个点，这个点没什么意义，f[1]=nums[0]，偷了第1个房间所产生的收益
    • 状态转移：f[i]表示偷了第i个房间产生的收益，要看其前1个房间，即不能偷前1个房间，即f[i-1],和前前1个房间，即f[i-2]，加上偷了第i个房间产生的收益，即f[i]=max{f[i-1],f[i-2]+nums[i-1]},代码如下：

image-20220305201642897.png

  1.         public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             if (n == 0) return 0;
  4.             int[] f = new int[n + 1];
  5.             f[0] = 0;
  6.             f[1] = nums[0];
  7.             for (int i = 2; i <= n; i++) {
  8.                 f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
  9.             }
  10.             return f[n];
  11.         }
  • 进而，我们其实发现，虽然上面的一维的空间优化很好了，但是发现在使用的时候，只用到了当前房间，前一个房间，前前一个房间，这几个变量，优化如下：
  1.         public int rob(int[] nums) {
  2.             //到达前一个房间时，获得的最大收益
  3.             int prev = 0;
  4.             int cur = 0;
  5.             for (int x : nums) {
  6.                 //max{前一个房间收益，前前一个房间收益+当前房间价值}
  7.                 int t = Math.max(cur, prev + x);
  8.                 //滚动
  9.                 prev = cur;
  10.                 cur = t;
  11.             }
  12.             return cur;
  13.         }

打家劫舍II

  1. 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
  3. 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
  7. 示例 1：
  9. 输入：nums = [2,3,2]
  10. 输出：3
  11. 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
  12. 示例 2：
  14. 输入：nums = [1,2,3,1]
  15. 输出：4
  16. 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
  17.      偷窃到的最高金额 = 1 + 3 = 4 。
  18. 示例 3：
  20. 输入：nums = [1,2,3]
  21. 输出：3
  24. 提示：
  26. 1 <= nums.length <= 100
  27. 0 <= nums[i] <= 1000

分析

本题区别于「打家劫舍I」是，第一间房间和最后一间房间是连着的，也就是头尾相连，「这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。」

方法1:暴力递归

与方法2合并，见方法2

方法2:自顶向下记忆化递归(Top-down)

  • sub_rob函数是取自「打家劫舍I」的记忆化递归的方式，记忆化递归实现，分两段找结果：
    • 偷第一间房间，也就意味着最后一间房一定不能偷，处理的是[0,n-2]区间
    • 不偷第一间房间，意味着最后一间房间可以偷也可以不偷，处理的是[1,n-1]区间
  1.         public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             if (n == 0) return 0;
  4.             if (n == 1) return nums[0];
  5.             //copyOfRange 函数取头不取尾，也就是[0,n-2]和[1,n-1]的范围
  6.             return Math.max(sub_rob(Arrays.copyOfRange(nums, 0, n - 1))
  7.                     , sub_rob(Arrays.copyOfRange(nums, 1, n)));
  8.         }
  11.         Integer[] memo;
  13.         public int sub_rob(int[] nums) {
  14.             memo = new Integer[nums.length];
  15.             return helper(nums, nums.length - 1);
  16.         }
  18.         public int helper(int[] nums, int i) {
  19.             if (i < 0) return 0;
  20.             if (memo[i] != null) return memo[i];
  21.             int steal = nums[i] + helper(nums, i - 2);
  22.             int non_steal = helper(nums, i - 1);
  23.             return memo[i] = Math.max(steal, non_steal);
  24.         }

方法3:自底向上填表DP(Bottom-up)

image-20220305220724142.png

  1.         public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             if (n == 0) return 0;
  4.             if (n == 1) return nums[0];
  5.             //f[i][0]表示没有偷第i间房间的前提下，[0,i]间房间所能获得的总收益
  6.             //f[i][1]表示偷第i间房间的前提下，[0,i]间房间所能获得的总收益
  7.             int[][] f = new int[n][2];
  8.             //不偷第一间
  9.             for (int i = 1; i < n; i++) {
  10.                 f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
  11.                 f[i][1] = f[i - 1][0] + nums[i];
  12.             }
  13.             //因为第一间房间没偷，所以最后一间房间时 偷或者不偷
  14.             //不偷：f[n - 1][0]
  15.             //偷 :  f[n - 1][1]
  16.             int x = Math.max(f[n - 1][1], f[n - 1][0]);
  17.             //偷了第一间房间
  18.             f[0][0] = 0;
  19.             f[0][1] = nums[0];
  20.             for (int i = 1; i < n - 1; i++) {
  21.                 f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
  22.                 f[i][1] = f[i - 1][0] + nums[i];
  23.             }
  24.             //因为第一间房间偷了，所以最后一间房间时 不能偷了，需要考虑倒数第二间房间是否偷了
  25.             //不偷：f[n - 2][0]
  26.             //偷 :  f[n - 2][1]
  27.             int y = Math.max(f[n - 2][0], f[n - 2][1]);
  28.             return Math.max(x, y);
  29.         }
  • 上面的写法是遍历了两遍nums，也可以采用一遍遍历的做法
    • 定义两个数组，prefix[n+1]和suffix[n+1]，前者表示偷了第一间房间（同时意味着最后一间房间一定不能偷），后者表示不偷第一间房间（同时意味着最后一间房间可以偷也可以不偷）
    • prefix[i]则表示在偷了第一间房间后，在[0,i-1]这个房间区间范围内获得的最大的收益
    • suffix[i]则表示在没有偷第一间房间后，在[0,i-1]这个房间区间范围内获得的最大的收益
    • 初始化时，要处理到第一间房间是否有收益，对于prefix和suffix是不同的
    • 返回结果时，返回**prefix**的倒数第二间房间时获得的最大收益和**suffix**的最后一间房间时获得的最大收益中的最大值
  1.         public int rob(int[] nums) {
  2.             int n = nums.length;
  3.             //处理一些边界返回
  4.             if (n == 0) return 0;
  5.             if (n == 1) return nums[0];
  6.             //偷第一间房
  7.             int[] prefix = new int[n + 1];
  8.             //不偷第一间房
  9.             int[] suffix = new int[n + 1];
  10.             //初始化
  11.             prefix[0] = 0;
  12.             prefix[1] = nums[0];
  13.             suffix[0] = 0;
  14.             suffix[1] = 0;
  15.             for (int i = 2; i <= n; i++) {
  16.                 prefix[i] = Math.max(prefix[i - 1], prefix[i - 2] + nums[i - 1]);
  17.                 suffix[i] = Math.max(suffix[i - 1], suffix[i - 2] + nums[i - 1]);
  18.             }
  19.             //prefix中的倒数第二件房间和suffix的最后一间房间  取最大值
  20.             return Math.max(prefix[n - 1], suffix[n]);
  21.         }
  • 另外一种写法
    • sub_rob函数是取自「打家劫舍I」的，状态转移方程见上面方法
  1. public int rob(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) return 0;
  4.     if (n == 1) return nums[0];
  5.     //copyOfRange 函数取头不取尾，也就是[0,n-2]和[1,n-1]的范围
  6.     return Math.max(sub_rob(Arrays.copyOfRange(nums, 0, n - 1))
  7.             , sub_rob(Arrays.copyOfRange(nums, 1, n)));
  8. }
  11. public int sub_rob(int[] nums) {
  12.     int n = nums.length;
  13.     if (n == 1) return nums[0];
  14.     int[] f = new int[n];
  15.     f[0] = nums[0];
  16.     f[1] = Math.max(nums[0], nums[1]);
  17.     for (int i = 2; i < n; i++) {
  18.         f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
  19.     }
  20.     return f[n - 1];
  21. }

打家劫舍III

image-20220306065009155.png

分析

区别于「打家劫舍I」和「打家劫舍II」这种数组模式的，本题是一个二叉树，但是也有相邻”房间”的概念，即父子节点相邻，如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

方法1:暴力递归

  • 定义函数
    • dfs(TreeNode root,boolean steal )处理当前节点root以及往下一层，当前节点是否打劫steal
  • 出口条件
    • 当到达叶子节点，也就是当前节点没有左右节点的时候，返回，且根据是否偷取当前节点返回金金额
  • 分支
    • 记录左右子树能获得的金额lv和rv
    • 当前节点root确定偷的时候,即**steal**为**true**的时候，去分别拿到当前节点root的左右子节点能带来的收益，而且要求左右子节点严格执行不偷
    • 当前节点root确定不偷的时候,即**steal**为**flase**的时候，去分别拿到当前节点root的左右子节点能带来的收益，区别于上面的情况，该情况下，当前节点的 左右子节点可以偷或者不偷，取最大值
  1.     public int rob(TreeNode root) {
  2.         return Math.max(dfs(root,false),dfs(root,true));
  3.     }
  5.     private int dfs(TreeNode root,boolean steal ){
  6.         if(root.left ==null && root.right ==null ) return steal? root.val:0;
  7.         int lv = 0, rv = 0;
  8.         if(steal){
  9.             if(root.left!=null) lv= dfs(root.left,false);
  10.             if(root.right!=null) rv = dfs(root.right,false);
  11.             return root.val+ lv+ rv;
  12.         }else{
  13.             if(root.left!=null) lv = Math.max(dfs(root.left,false),dfs(root.left,true));
  14.             if(root.right!=null) rv = Math.max(dfs(root.right,false),dfs(root.right,true));
  15.            return lv+ rv;
  16.         }

很不幸，上面这种普通的递归方式，没有通过所有的case，显示的TLE了，但说明思路是对的，继续优化

方法2:自顶向下记忆化递归(Top-down)

image-20220306113831917.png

接上面的暴力递归的方法，刚开始使用了一个map来记忆化TreeNode节点的值，总是不过，后来发现是因为定义了steal和non_steal两种状态，相应的TreeNode也应该有两个状态，结合着返回

  1.         //记忆化，按steal和non_steal存两份，写法丑陋~
  2.         Map<TreeNode, Integer> steal_map = new HashMap<>();//steal
  3.         Map<TreeNode, Integer> non_steal_map = new HashMap<>();//non_steal
  5.         public int rob(TreeNode root) {
  6.             if (root == null) return 0;
  7.             if (root.left == null && root.right == null) return root.val;
  8.             return Math.max(dfs(root, true), dfs(root, false));
  10.         }
  12.         private int dfs(TreeNode root, boolean visit) {
  13.             if (root.left == null && root.right == null) return visit ? root.val : 0;
  14.             //这里如果两个map都有值，需要结合visit状态来选，只有一个map有值的情况也很类似
  15.             if (steal_map.containsKey(root) && non_steal_map.containsKey(root))
  16.                 return visit ? steal_map.get(root) : non_steal_map.get(root);
  17.             if (visit && steal_map.containsKey(root)) return steal_map.get(root);
  18.             if (!visit && non_steal_map.containsKey(root)) return non_steal_map.get(root);
  19.             int leftValue = 0, rightValue = 0;
  20.             if (visit) {
  21.                 if (root.left != null) leftValue = dfs(root.left, false);
  22.                 if (root.right != null) rightValue = dfs(root.right, false);
  23.                 int res = root.val + leftValue + rightValue;
  24.                 steal_map.put(root, res);
  25.                 return res;
  26.             } else {
  27.                 if (root.left != null) leftValue = Math.max(dfs(root.left, true), dfs(root.left, false));
  28.                 if (root.right != null) rightValue = Math.max(dfs(root.right, true), dfs(root.right, false));
  29.                 int res = leftValue + rightValue;
  30.                 non_steal_map.put(root, res);
  31.                 return res;
  32.             }
  33.         }

基于上图，有另外一种递归的写法

  1. Map<TreeNode, Integer> memo = new HashMap<>();
  3. public int rob(TreeNode root) {
  4.     if (root == null) return 0;
  5.     if (memo.containsKey(root)) return memo.get(root);
  6.     int val = 0;
  7.     if (root.left != null) {
  8.         val += rob(root.left.left) + rob(root.left.right);
  9.     }
  10.     if (root.right != null) {
  11.         val += rob(root.right.left) + rob(root.right.right);
  12.     }
  13.       //
  14.     int steal = root.val + val;
  15.     int non_steal = rob(root.left) + rob(root.right);
  16.     int res = Math.max(steal, non_steal);
  17.     memo.put(root, res);
  18.     return res;
  19. }

方法3:自底向上填表DP(Bottom-up)

对于当前节点，有两个处理状态

  • 选择偷当前节点，那么这时候，当前节点的两个儿子节点则不能偷了
    • 当前节点获得的最大金额=左孩子所能获得的最大金额+右孩子所能获得的最大金额
    • 其中左孩子所能获得的最大金额和左孩子偷与不偷无关联关系，对于右孩子，同理
  • 选择不偷当前节点，那么这时候，当前节点的两个儿子节点只需要返回一个最大的金额即可，即：
    • 当前节点获得的最大金额=当前节点的价值+不偷左孩子所能获得最大金额+不偷右孩子所能获得的最大金额
  1.          public int rob(TreeNode root) {
  2.                 int[] t = rob_sub(root);
  3.                 return Math.max(t[0], t[1]);
  4.             }
  6.             private int[] rob_sub(TreeNode root) {
  7.                 if (root == null) return new int[2];
  8.                 int[] t = new int[2];
  9.                 //当前节点的左孩子节点所能带来的偷|不偷带来的最大金额 left_values -> lvs
  10.                 int[] lvs = rob_sub(root.left);
  11.                 //当前节点的右孩子节点所能带来的偷|不偷带来的最大金额 right_values -> rvs
  12.                 int[] rvs = rob_sub(root.right);
  13.                 //[0]表示当前节点不偷，[1]表示当前节点偷了
  14.                 t[0] = Math.max(lvs[0], lvs[1]) + Math.max(rvs[0], rvs[1]);
  15.                 t[1] = root.val + lvs[0] + rvs[0];
  16.                 return t;
  17.         }