House Robber III

Question (LC.337)

Now you decide to rob a neighborhood that's more challenging. The neighborhood's structure is a binary tree. The constraint is that you cannot rob two directed linked houses. Return the maximum amount of money you can rob at given neighborhood.

Analysis

Subtree DP =͟͟͞͞•̫͡•ʔ Firstly, since the tree node is defined to hold only the money value, we have to figure out a way to memoize the partial solutions at each node. A structure like Map<TreeNode, Integer> will work fine. Secondly, the constraint is that we cannot rob two directly linked houses. So which order should we visit the nodes? Either preorder or postorder. (inorder doesn't make sense since cause you can't make a decision on to rob or not to rob base on one child).

Approach

1. define optimal subproblems - by subtree
    rob(root) = maximum amount of money you can rob at the subtree starting from root
2. solve by subtree, again 2 options, to rob at root or skip it
    rob(root) = Math.max(root.value + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) 
                                    + rob(root.right.right), rob(root.left) + rob(root.right));
3. topo order
    from leaf nodes to the root
4. init base cases
    if (root == null) return 0
5. answer
    return memo.get(root)

Code

public int rob(TreeNode root) {
    // edge cases
    if (root == null) {
        return 0;
    }
    // create memo table
    Map<TreeNode, Integer> memo = new HashMap<>();
    // fill in the memo table
    robHelper(root, memo);
    // answer
    return memo.get(root);
}

private int robHelper(TreeNode root, Map<TreeNode, Integer> memo) {
    // base case
    if (root == null) {
        return 0;
    }
    if (memo.containsKey(root)) {
        return memo.get(root);
    }
    // divide & conquer style
    int leftLeftSubtree = 0;
    if (root.left != null) {
        leftLeftSubtree = robHelper(root.left.left, memo) + robHelper(root.left.right, memo);
    }
    int rightRightSubtree = 0;
    if (root.right != null) {
        rightRightSubtree = robHelper(root.right.left, memo) + robHelper(root.right.right, memo);
    }
    // recurrence
    int maxEarning = Math.max(root.val + leftLeftSubtree + rightRightSubtree, 
                              robHelper(root.left, memo) + robHelper(root.right, memo));
    // memoization
    memo.put(root, maxEarning);
    return maxEarning;
}

Time & Space Complexity

Time - O(V) Space - O(V) since we memoize at every node

Follow Up #3

Can you solve question 3 in in O(1) space?

Analysis

The approach above is essentially recursion and memoization which requires O(#subproblems) space. O(1) space is usually asking for the bottom up approach - tabulation. Before we build this tree bottom up, we need to revisit how we defined the (optimal) subproblems. The way we firstly defined the subproblems is optimal not very efficient. The newly defined subproblems can still overlap with each other (see maxEarning). Instead, we want to distinguish the two possible options - rob and not rob. We want to keep track of them at each node to build this implicit memoization tree bottom up.

Updated Code

class ReturnType {
    int rob;
    int notRob;
    ReturnType(int val1, int val2) {
        rob = val1;
        notRob = val2;
    }
}

public int rob(TreeNode root) {
    ReturnType result = robHelper(root);
    return Math.max(result.rob, result.notRob);
}

private ReturnType robHelper(TreeNode root) {
    // base case
    if (root == null) {
        return new ReturnType(0, 0);
    }
    // divide & conquer (post-order traversal)
    ReturnType leftSubtree = robHelper(root.left);
    ReturnType rightSubtree = robHelper(root.right);
    // recurrence & merge
    int rob = root.val + leftSubtree.notRob + rightSubtree.notRob;
    int notRob = Math.max(leftSubtree.rob, leftSubtree.notRob) +
                 Math.max(rightSubtree.rob, rightSubtree.notRob);
    return new ReturnType(rob, notRob);
}

Time & Space Complexity

Time - O(V) visiting all the nodes

Space - O(1) only keeping track of a tuple of 2 elements (not counting stack frame)

Conclusion

As we have seen from the last question, the challenging part of DP is defining the subproblems in a desirable way. Hopefully, the intuition will be built up after some practices for each paradigm. Here is a quote from the founder of set theory. "To ask the right question is harder than to solve it." -- Georg Cantor

＼ʕ •ᴥ•ʔ＼