Java DP solution with explanation

• ``````/**
* 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;
}
}
}
}``````

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