Java DP solution with explanation


  • 1
    C
    /**
     * Let S(k, r) represent the state of robbed money, where k is current node and r is whether to rob k (=1) or not (=0),
     * therefore, S(k, r) can be read as "the amount of money can be robbed at node k, either to rob k (r=1) or not to rob k (r=0)"
     *
     * Then, the state can be calculated via:
     *   S(k,0) = max{S(k.left, 0), S(k.left, 1)} + max{S(k.right, 0), S(k.right, 1)}
     *   S(k,1) = k.val + S(k.left, 0) + S(k.right, 0)
     * 
     * Finally, the max amount of money can be robbed at root node is max{S(root,0), S(root,1)}
     */
    public class Solution {
    
        private Map<TreeNode, Integer> rob = new HashMap<>();
        private Map<TreeNode, Integer> norob = new HashMap<>();
    
        public int rob(TreeNode root) {
            return Math.max(robHelper(root, true), robHelper(root, false));
        }
        
        private int robHelper(TreeNode root, boolean robRoot) {
            if (root == null) {
                return 0;
            }
            
            if (robRoot) {
                if (rob.containsKey(root)) {
                    // Solved case
                    return rob.get(root);
                } else {
                    int money = root.val + robHelper(root.left, false) + robHelper(root.right, false);
                    rob.put(root, money);
                    return money;
                }
            } else {
                if (norob.containsKey(root)) {
                    // Solved case
                    return norob.get(root);
                } else {
                    int leftMax = Math.max(robHelper(root.left, false), robHelper(root.left, true));
                    int rightMax = Math.max(robHelper(root.right, false), robHelper(root.right, true));
                    int money = leftMax + rightMax;
                    norob.put(root, money);
                    return money;
                }
            }
        }
    }

Log in to reply
 

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