Leetcode-cn.com/problems/ho…

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.

Train of thought

Maximum value: exhaustive dynamic programming

Base case: null 0;

Status: the amount stolen, that is, the nodes and that are not directly adjacent

Select: it is not adjacent to the node

Bp function: need to realize the calculation of the maximum amount;

Bp function analysis: when you come to a node, there are two situations: 1) choose to steal it, and then choose to steal its grandson node. 2) Choose not to steal it, and then steal its child node. Compare the size of the two values and return the stolen amount

You can use memos to keep track of stolen nodes

code

public int rob(TreeNode root) { HashMap<TreeNode,Integer> map = new HashMap<>(); return bp(root,map); } public int bp(TreeNode root,HashMap<TreeNode,Integer> map){ if (root==null){ return 0; } if (map.containsKey(root)){ return map.get(root); } int l = bp(root.left,map); int r = bp(root.right,map); int a = l+r; int b = root.val; if (root.left ! = null){ b += bp(root.left.left,map)+bp(root.left.right,map); } if (root.right ! = null){ b += bp(root.right.left,map)+bp(root.right.right,map); } map.put(root,Math.max(a,b)); return Math.max(a,b); }}Copy the code

debug

Public int rob(TreeNode root) {HashMap<TreeNode,Integer> map = new HashMap<>(); return bp(root,map); } public int bp(TreeNode root,HashMap<TreeNode,Integer> map){ if (root==null){ return 0; } if (map.containsKey(root)){ return map.get(root); } int l = bp(root.left,map); int r = bp(root.right,map); Int a = l+r; Int b = root.val; if (root.left ! = null){ b += bp(root.left.left,map)+bp(root.left.right,map); } if (root.right ! = null){ b += bp(root.right.left,map)+bp(root.right.right,map); } // put map.put(root, math.max (a,b)); // return math.max (a,b); }}Copy the code

If you want to callroot.left.rightThe need toroot.leftPerform NULL judgment

Code optimization

Each node can choose to steal or not steal two states. According to the meaning of the question, connected nodes cannot steal together

Int [] res = new int[2] 0 indicates no stealing. 1 represents the state of stealing the maximum amount of money that any node can steal

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

The states of the left and right subtrees affect the states of the current subtree, but the states of the other subtrees do not. Therefore, there is no need to use map to record the state of each subtree. Recursion always returns the solution of the child call to the parent call, so just use two variables in each recursion to store the two states of the current child problem and return them to the parent call.)

Step 1: state definition dp[node][j] : here node represents a node, node as the root of the tree, and specifies whether the node can steal the maximum value.

J = 0 indicates that node nodes are not stolen; J = 1 indicates that node is stolen. Step 2: Derive the state transition equation. Depending on whether the current node steals or does not steal, the corresponding state in the child node needs to be transferred from it.

If the current node does not steal, the left and right children can steal or do not steal, choose the largest node; If the current node steals, the left and right children cannot be stolen. (The state transition equation is a little complicated, so look directly at the code.)

Step 3: initialize no node, empty node, return 0, corresponding to the recursive termination condition during the sequence traversal;

Step 4: Output at the root, return the greater of the two states.

Step 5: Think about optimizing space.

(Author: Liweiwei1419 Link: leetcode-cn.com/problems/ho…)

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]; // return new int[]{0, 0}} int[] res =new int[2]; int[] left =bp(root.left); int[] right = bp(root.right); res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]); res[1] = root.val + left[0] +right[0]; return res; }}Copy the code