题目链接
打家劫舍 III
题目描述
注意点
- 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警
- 返回 在不触动警报的情况下 ,小偷能够盗取的最高金额
解答思路
- 记忆化 + 解决重复子问题解决本题,在任意一个位置,小偷可以选择打劫该房屋和不打劫该房屋,如果打劫,则不能打劫该节点下的子节点,如果不打劫,则该节点下的子节点可以选择打劫也可以选择不打劫,可以转换为动态规划的问题:任意一个位置处能够盗取的最大金额为其子节点能够盗取的最大金额之和或其本身加上其孙子节点能够盗取的最大金额之和的最大值,为了防止同一个节点的最大金额重复计算,可以使用Map存储每个节点的最大金额
- 参考题解在任意一个节点时,可以用大小为2的数组result存储该节点的两种情况:也就是result[0]为不抢劫该节点的最大金额,result[1]为抢劫该节点的最大金额
代码
方法一:文章来源:https://www.toymoban.com/news/detail-708418.html
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;
}
}
方法二:文章来源地址https://www.toymoban.com/news/detail-708418.html
// 优化版
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;
}
}
关键点
- 动态规划的思想
到了这里,关于打家劫舍 III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!