Python solution with detailed explanation


  • 0
    G

    Solution

    House Robber III https://leetcode.com/problems/house-robber-iii/?tab=Description

    https://discuss.leetcode.com/topic/39834/step-by-step-tackling-of-the-problem/2

    Dynamic Programming

    • Simple recursive formulation with a cache.
    class Solution(object):
        def dfs(self, root, cache):
            if root == None:
                return 0
            elif root in cache:
                return cache[root]
            else:
                inc = root.val
                if root.left:
                    inc = inc + self.dfs(root.left.left, cache) + self.dfs(root.left.right, cache)
                if root.right:
                    inc = inc + self.dfs(root.right.left, cache) + self.dfs(root.right.right, cache)
                exc = self.dfs(root.left, cache) + self.dfs(root.right, cache)
                cache[root] = max(inc, exc)
                return cache[root]
    
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            return self.dfs(root, {})
    

    Solution using Post Order

    • Every node returns two values - rob including root.val, rob excluding root.val.
    • Now we find inc, exc values for left subtree and right subtree.
    • How do we combine these values with root.val to return the inc, exc for current node?
    • inc = root.val + exc1 + exc2
    • exc = max(inc1, exc1) + max(inc2, exc2)
    class Solution(object):
        def dfs(self, root):
            if root == None:
                return 0,0
            inc1, exc1 = self.dfs(root.left)
            inc2, exc2 = self.dfs(root.right)
            inc = root.val + exc1 + exc2
            exc = max(inc1, exc1) + max(inc2, exc2)
            return inc, exc
    
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            return max(self.dfs(root))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.