Leetcode #337 House Robber III

[yokostan]

Recursive: super slow, beats 20%:

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int val = 0;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
    }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
    }

        return Math.max(val + root.val, rob(root.left) + rob(root.right));
    }
}

Let's think about DP, beats 100%:

class Solution {
    public int rob(TreeNode root) {
        int[] ans = dp(root);
        return Math.max(ans[0], ans[1]);
    }

    public int[] dp(TreeNode root) {
        if (root == null) {
            return new int[] {0, 0};
        }
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        int[] curr = new int[2];
        curr[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        curr[1] = root.val + left[0] + right[0];
        return curr;
    }
}

This is just genius. dp[0] means we don't use the root element, dp[1] means we use the root element. For each root, we can either use or not use and this turns into a binary classification. We can simply recurse on this dp array and this saves us lots of time and space.