【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划

简介: 【每日一题Day330】LC337打家劫舍Ⅲ | 动态规划

打家劫舍Ⅲ【LC337】

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/house-robber-iii

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

果然是 (线下面试 忙忘了)

DFS【超时】

如果抢了当前节点,两个孩子就不能动,如果没抢当前节点,就可以考虑抢左右孩子,最后取最大值返回

// 有重复计算
 // 1.递归去偷,超时
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money, rob(root.left) + rob(root.right));
    }

复杂度


时间复杂度:O(n^2)

空间复杂度:O ( l o g n )

DFS 使用map集合存放计算的结果
  // 2.递归去偷,记录状态
    // 执行用时:3 ms , 在所有 Java 提交中击败了 56.24% 的用户
    public int rob1(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;
    }

复杂度

时间复杂度:O ( n )

空间复杂度:O ( l o g n )

树形dp

  1. 确定递归函数的参数和返回值

参数:node

返回值:长度为2的dp数组,存放偷或者不偷的结果

下标为0记录不偷该节点所得到的的最大金钱

下标为1记录偷该节点所得到的的最大金钱。

  1. 确定终止条件

空节点时返回,{0,0}【相当于dp数组的初始化】

  1. 确定遍历顺序

后序遍历

  1. 确定单层递归逻辑

如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0];

如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

  1. 举例推导dp

代码

// 不偷:Max(左孩子不偷,左孩子偷) + Max(右孩子不偷,右孩子偷)
    // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    // Math.max(rob(root.right)[0], rob(root.right)[1])
    // 偷:左孩子不偷+ 右孩子不偷 + 当前节点偷
    // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    public int rob3(TreeNode root) {
        int[] res = robAction1(root);
        return Math.max(res[0], res[1]);
    }
    int[] robAction1(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;
        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }

复杂度

时间复杂度:O ( n )

空间复杂度:O ( l o g n )

目录
相关文章
|
7月前
【每日一题Day273】LC860柠檬水找零 | 贪心
【每日一题Day273】LC860柠檬水找零 | 贪心
42 0
【每日一题Day273】LC860柠檬水找零 | 贪心
|
7月前
【每日一题Day366】LC2103环和杆 | 状态压缩
【每日一题Day366】LC2103环和杆 | 状态压缩
48 0
|
7月前
|
算法
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
55 0
|
7月前
【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心
【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心
39 0
|
7月前
|
存储 人工智能 算法
【每日一题Day348】LC137只出现一次的数字Ⅱ | 状态转移
【每日一题Day348】LC137只出现一次的数字Ⅱ | 状态转移
49 0
|
7月前
蓝桥备战--分糖果OJ2928 贪心 分类讨论
蓝桥备战--分糖果OJ2928 贪心 分类讨论
67 0
|
7月前
【每日一题Day329】LC213打家劫舍Ⅱ | 动态规划
【每日一题Day329】LC213打家劫舍Ⅱ | 动态规划
40 0
|
7月前
【每日一题Day328】LC198打家劫舍 | 动态规划
【每日一题Day328】LC198打家劫舍 | 动态规划
53 0
|
7月前
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
52 0
|
7月前
|
图计算
【每日一题Day274】LC42接雨水 | 单调栈
【每日一题Day274】LC42接雨水 | 单调栈
51 0