• 打家劫舍 III


    题目链接

    打家劫舍 III

    题目描述


    注意点

    • 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警
    • 返回 在不触动警报的情况下 ,小偷能够盗取的最高金额

    解答思路

    • 记忆化 + 解决重复子问题解决本题,在任意一个位置,小偷可以选择打劫该房屋和不打劫该房屋,如果打劫,则不能打劫该节点下的子节点,如果不打劫,则该节点下的子节点可以选择打劫也可以选择不打劫,可以转换为动态规划的问题:任意一个位置处能够盗取的最大金额为其子节点能够盗取的最大金额之和其本身加上其孙子节点能够盗取的最大金额之和的最大值,为了防止同一个节点的最大金额重复计算,可以使用Map存储每个节点的最大金额
    • 参考题解在任意一个节点时,可以用大小为2的数组result存储该节点的两种情况:也就是result[0]为不抢劫该节点的最大金额,result[1]为抢劫该节点的最大金额

    代码

    方法一:

    class Solution {
        public int rob(TreeNode root) {
            Map<TreeNode, Integer> map = new HashMap<>();
            return robInterval(root, map);
        }
    
        public int robInterval(TreeNode root, Map<TreeNode, Integer> map) {
            if (root == null) {
                return 0;
            }
            if (map.get(root) != null) {
                return map.get(root);
            }
            int money = root.val;
            if (root.left != null) {
                money = money + robInterval(root.left.left, map) + robInterval(root.left.right, map);
            }
            if (root.right != null) {
                money = money + robInterval(root.right.left, map) + robInterval(root.right.right, map);
            }
            int maxVal = Math.max(money, robInterval(root.left, map) + robInterval(root.right, map));
            map.put(root, maxVal);
            return maxVal;
        }
    }
    
    • 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

    方法二:

    // 优化版
    class Solution {
        public int rob(TreeNode root) {
            // 0不抢劫,1抢劫
            int[] result = robInternal(root);
            return Math.max(result[0], result[1]);
        }
    
        public int[] robInternal(TreeNode root) {
            if (root == null) {
                return new int[2];
            }
            int[] leftVal = robInternal(root.left);
            int[] rightVal = robInternal(root.right);
            int[] result = new int[2];
            result[0] = Math.max(leftVal[0], leftVal[1]) + Math.max(rightVal[0], rightVal[1]);
            result[1] =  root.val + leftVal[0] + rightVal[0];
            return result;
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    关键点

    • 动态规划的思想
  • 相关阅读:
    Qt5.15添加dll库如何指定库文件路径?
    Linux进程基本知识详解
    注解处理器(APT)是什么?
    提名 Apache ShardingSphere Committer,说说方法
    我辞职了!“没有Python编程经验的我,连简历都不敢投”
    Mempool Library
    leetcode 148. Sort List 排序链表(中等)
    String, Int 和 Byte数组
    Anaconda下的pkgs占用空间13G,如何安全的清理(已解决)
    使用Flink处理Kafka中的数据_题库子任务_Java语言实现
  • 原文地址:https://blog.csdn.net/weixin_51628158/article/details/132801033