House Robber III

To solve the House Robber III problem, we use a dynamic programming approach combined with depth-first search (DFS) to determine the maximum amount of money a thief can steal without robbing two directly connected houses. Here’s a structured explanation:

Approach

1. Problem Analysis: The binary tree structure represents houses, where each node is a house. The thief cannot rob two directly connected nodes (parent and child). The goal is to maximize the stolen amount under this constraint.

2. Dynamic Programming with DFS: For each node, compute two scenarios:

   • Rob the current node: Add the node’s value to the maximum amounts from not robbing its children.
   • Do not rob the current node: Take the maximum of robbing or not robbing each child and sum these values.

3. Recursive Helper Function: A helper function dfs(node) returns a tuple (rob, not_rob):

   • rob is the maximum value if the current node is robbed.
   • not_rob is the maximum value if the current node is not robbed.

4. Base Case: For a null node, both values are 0.

5. Post-order Traversal: Compute values for children first, then determine the current node’s values based on its children.

Solution Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)
        # If we rob the current node, we cannot rob its children
        rob = node.val + left[1] + right[1]
        # If we don't rob, take max of robbing/not robbing children
        not_rob = max(left) + max(right)
        return (rob, not_rob)
    
    return max(dfs(root))

Explanation

• Recursive DFS Traversal: The dfs function visits each node once, starting from the leaves and moving up to the root.
• Decision at Each Node:
  • Rob Current Node: rob = node.val + left[1] + right[1] (using the not_rob values of children).
  • Do Not Rob Current Node: not_rob = max(left, left[1]) + max(right, right[1]) (choosing the best from each child).
• Final Result: The maximum of the two values returned by dfs(root) gives the optimal solution.

This approach efficiently computes the result in $O(n)$ time, where $n$ is the number of nodes, as each node is processed exactly once[1][2][4].

Citations: [1] https://algo.monster/liteproblems/337 [2] https://www.youtube.com/watch?v=Nt0IqkcxG80 [3] https://washifu.github.io/codeblog/pages/2017-10-19-House_Robber_III/ [4] https://leetcode.com/problems/house-robber-iii/ [5] https://www.youtube.com/watch?v=nHR8ytpzz7c [6] https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0337.House%20Robber%20III/README_EN.md [7] https://walkccc.me/LeetCode/problems/337/ [8] https://leetcode.com/problems/house-robber-iii/solution/

---

Resposta do Perplexity: pplx.ai/share