【LeetCode】动态规划—337. 打家劫舍 III（附完整Python/C++代码）

题目描述

前言

打家劫舍 III 是 打家劫舍 系列问题中的一个变种。这里的房屋排列不再是线性排列，而是形成了一棵二叉树，每个节点代表一个房子，每个房子内有一定的钱。相邻的房子（即父子关系）不能同时被抢。我们的目标是找出在这棵二叉树中，能够抢劫到的最大金额。

---

基本思路

1. 问题定义

给定一个二叉树结构，每个节点表示一个房子，房子里有一定的钱，要求我们在不抢劫相邻房子的情况下，抢劫到的最大金额。

二叉树的限制：

• 每个房子与其子房子相邻，如果父节点被抢劫，那么子节点不能被抢。
• 可以选择抢劫或不抢劫某个房子。

2. 理解问题和递推关系

核心思路：

对于每个节点，我们有两种选择：

1. 抢劫当前节点：如果抢劫当前节点，那么它的左右子节点不能被抢劫。
2. 不抢劫当前节点：如果不抢劫当前节点，那么我们可以选择是否抢劫它的左右子节点。

状态定义：

• 对于每个节点 root，我们定义两个状态：
  1. rob(root)：表示抢劫当前节点时能够获得的最大收益。
  2. not_rob(root)：表示不抢劫当前节点时能够获得的最大收益。

状态转移方程：

1. 如果抢劫当前节点：那么最大收益为当前节点的值 root.val 加上不抢劫左右子节点的收益：
   $$rob(root)=root.val+not\_rob(root.left)+not\_rob(root.right)$$

2. 如果不抢劫当前节点：那么最大收益为抢劫或不抢劫左右子节点中的最大值：
   $$not\_rob(root)=\max (rob(root.left),not\_rob(root.left))+\max (rob(root.right),not\_rob(root.right))$$

递归求解：

我们从树的根节点开始，递归地计算每个节点的抢劫和不抢劫情况下的最大收益。最终的结果是根节点抢劫和不抢劫情况下的最大值。

3. 解决方法

递归 + 动态规划方法

1. 对于每个节点，使用递归来计算它的抢劫和不抢劫情况下的最大收益。
2. 使用 postorder（后序遍历）的方式，先计算子节点的收益，再计算父节点的收益。
3. 递归的终止条件是到达叶子节点的空节点，返回 (0, 0)，即抢劫和不抢劫的收益都是 0。

伪代码：

function rob(root):
    if root is None:
        return (0, 0)
    
    left = rob(root.left)
    right = rob(root.right)
    
    rob_current = root.val + left[1] + right[1]
    not_rob_current = max(left[0], left[1]) + max(right[0], right[1])
    
    return (rob_current, not_rob_current)

result = rob(root)
return max(result[0], result[1])

4. 进一步优化

• 空间优化：由于我们是通过递归的方式求解，每个节点只需要存储它左右子节点的结果，因此不需要额外的存储空间，空间复杂度可以保持在 O(h)，其中 h 是树的高度。
• 时间复杂度：时间复杂度为 O(n)，因为每个节点只被遍历一次。

5. 小总结

• 问题思路：通过动态规划自底向上的递归求解树中每个节点的最大收益。
• 递归的应用：后序遍历是解决树结构动态规划问题的常用方式，因为我们需要先计算子节点的结果，再计算父节点的结果。
• 时间复杂度：时间复杂度为 O(n)，适合处理大规模的二叉树输入。

以上就是打家劫舍 III问题的基本思路。

---

Python代码

class Solution:
    def rob(self, root: TreeNode) -> int:
        # 返回 (抢劫当前节点的最大收益, 不抢劫当前节点的最大收益)
        def helper(node):
            if not node:
                return (0, 0)
            
            left = helper(node.left)
            right = helper(node.right)
            
            # 抢劫当前节点的收益
            rob_current = node.val + left[1] + right[1]
            # 不抢劫当前节点的收益
            not_rob_current = max(left[0], left[1]) + max(right[0], right[1])
            
            return (rob_current, not_rob_current)
        
        # 计算根节点的抢劫与不抢劫的最大收益
        result = helper(root)
        # 返回两种情况中的最大值
        return max(result[0], result[1])

Python代码解释

1. 递归定义：定义一个递归函数 helper(node)，返回两个值：抢劫当前节点的最大收益和不抢劫当前节点的最大收益。
2. 状态转移：根据状态转移方程计算当前节点的最大收益。
3. 返回结果：最终返回根节点抢劫和不抢劫情况下的最大值。

---

C++代码

class Solution {
public:
    pair<int, int> helper(TreeNode* node) {
        if (!node) return {0, 0};
        
        pair<int, int> left = helper(node->left);
        pair<int, int> right = helper(node->right);
        
        // 抢劫当前节点的最大收益
        int rob_current = node->val + left.second + right.second;
        // 不抢劫当前节点的最大收益
        int not_rob_current = max(left.first, left.second) + max(right.first, right.second);
        
        return {rob_current, not_rob_current};
    }
    
    int rob(TreeNode* root) {
        pair<int, int> result = helper(root);
        return max(result.first, result.second);
    }
};

C++代码解释

1. 递归定义：定义一个递归函数 helper(node)，返回一对值，表示抢劫和不抢劫当前节点的最大收益。
2. 状态转移：通过递归后序遍历计算每个节点的最大收益。
3. 返回结果：最终返回根节点抢劫和不抢劫的最大值。

---

总结

• 核心思路：通过递归的方式，后序遍历二叉树，计算每个节点的抢劫和不抢劫两种状态下的最大收益。
• 动态规划递归：使用递归的方式自底向上计算每个节点的最优解。通过状态转移方程，能够有效地解决这个树形结构的动态规划问题。
• 时间复杂度：该算法的时间复杂度为 O(n)，空间复杂度为 O(h)，其中 n 是节点数量，h 是树的高度。

原文地址：https://blog.csdn.net/AlbertDS/article/details/142897430

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！