The title

After robbing a street and a circle of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the Root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that “all the houses in this place are arranged like a binary tree.” If two directly connected houses are robbed on the same night, the house will automatically alarm the police. Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.

From leetcode-cn.com/problems/ho…

Idea + code

Find the best value, exhaustive, BP problem. So let’s just define the state transition equation, so the BP function is going to be the maximum amount of money that this node can steal

There are two scenarios for each node: 1. Steal this node and then steal its grandchildren; 2. Don’t steal this node and then steal its children.

Base case is null

And then the return value is the maximum amount of money that this node can steal, which is the Max of these two, and remember to optimize with the memo.

Public int rob(TreeNode root) {public int rob(TreeNode root) { HashMap<TreeNode,Integer> Memo = new HashMap<>(); return tou(root,memo); } public int tou(TreeNode root,HashMap<TreeNode,Integer> memo){ // base case if (root == null){ return 0; } if(memo.containsKey(root)){ return memo.get(root); } // state transition equation int res = root.val; if(root.left ! = null){ res += tou(root.left.left,memo)+tou(root.left.right,memo); } if(root.right ! = null){ res += tou(root.right.left,memo)+tou(root.right.right,memo); } int result = Math.max(res,tou(root.right,memo)+tou(root.left,memo)); // Add memo.put(root,result); return result; }}Copy the code

Optimize the compression

Since there are only two steal and no-steal states for each node, only two states need to be stored. 0 means not stealing, 1 means stealing. Is:

The maximum amount of money any node can steal can be defined as

Current node chooses not to steal: Maximum amount of money that the current node can steal = Maximum amount of money that the left child can steal + Amount of money that the right child can steal: Maximum amount of money that the current node can steal = Maximum amount of money that the left child can steal + Amount of money that the right child can steal + amount of money that the current node can steal

Write the following code directly, there is a problem:

class Solution { public int rob(TreeNode root) { int [] result = bp(root); return Math.max(result[0],result[1]); } public int[] bp(TreeNode root){ if(root == null){ return new int[2]; } int[] res =new int[2]; int[] left = bp(root.left); int[] right = bp(root.right); res[0] = left[1]+right[1]; res[1] = root.val + left[0] +right[0]; return res; }}Copy the code

There is a problem with this code:

Even when this node is not stolen, its left and right nodes can not be stolen (across two levels, as long as the maximum value).

class Solution { public int rob(TreeNode root) { int [] result = bp(root); return Math.max(result[0],result[1]); } public int[] bp(TreeNode root){ if(root == null){ return new int[2]; } int[] res =new int[2]; int[] left = bp(root.left); int[] right = bp(root.right); // res[0] = left[1]+right[1]; res[0] = Math.max(left[1],left[0])+Math.max(right[1],right[0]); res[1] = root.val + left[0] +right[0]; return res; }}Copy the code