TyranitarX Connect.

LeetCode每日打卡-2020.8.5

算法
Word count: 633Reading time: 2 min
2020/08/05 Share

2020.8.5 每日题解 LeetCode 337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1


输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

1
2
3
4
5
6
7
8
9
10
输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

思路详解

在这里提供两种方法
1、暴力递归（最优子结构
从题目中可以得到最小单元为父亲->孙子 或者 儿子->
即求 父亲+4个孙子 VS 两个儿子 偷到的钱谁更多

2、重新定义思路优化
每个节点可以选择偷或者不偷，相连着的节点不能同时偷，也就是说
父亲偷了 儿子就不能偷 =父节点偷的钱+四个孙子偷的钱
father偷.val + left不偷.val +right不偷.val
儿子偷了 孙子就不能偷 = 两个儿子偷的钱
Max（left不偷.val,left偷.val) + Max(right不偷.val+right偷.val)

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import javax.print.DocFlavor;
import java.util.HashMap;

public class M337_rob {
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        HashMap<TreeNode, Integer> temps = new HashMap<>();
        int result[] = doRob2(root);
        return Math.max(result[0], result[1]);
    }

    //记忆化搜索递归DP
    public int doRob(TreeNode root, HashMap<TreeNode, Integer> temps) {
        if (root == null)
            return 0;
        if (temps.containsKey(root))
            return temps.get(root);
        int money = root.val;
        if (root.left != null) {
            money += doRob(root.left.left, temps) + doRob(root.left.right, temps);
        }
        if (root.right != null) {
            money += doRob(root.right.left, temps) + doRob(root.right.right, temps);
        }
        int result = Math.max(money, doRob(root.left, temps) + doRob(root.right, temps));
        temps.put(root, result);
        return result;
    }

    //dp降维优化
    public int[] doRob2(TreeNode root) {
        if (root == null)
            return new int[2];
        int val = root.val;
        int[] result = new int[2];
        int[] left = doRob2(root.left);
        int[] right = doRob2(root.right);

        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = val + left[0] + right[0];
        return result;
    }
}

Author：TyranitarX

原文链接：http://tyranitarx.github.io/2020/08/05/LeetCode%E6%AF%8F%E6%97%A5%E6%89%93%E5%8D%A1-2020-8-5/

发表日期：August 5th 2020, 11:40:16 am

更新日期：August 11th 2020, 10:14:11 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 2020.8.5 每日题解 LeetCode 337. 打家劫舍 III
    1. 1.0.1. 思路详解
Total : 20
2020
2019
machine learning deep learning TensorFlow 前端 算法