Subject to introduce

Force buckle 337: leetcode-cn.com/problems/ho…

Solution 1. Violent recursion – optimal substructure

In solution 1 and solution 2, we use the grandfather, two children, and four grandchildren to illustrate the problem. First, we define the state of the problem, where the grandfather node gets the maximum amount of stolen money

First of all, it should be clear that the adjacent nodes cannot be stolen, that is, if the grandfather chooses to steal, the son cannot steal, but the grandson can steal. There are only about two children in a binary tree, and a grandfather can have at most two sons and four grandchildren

According to the above conditions, we can figure out how to calculate the money of a single node?

The combination of 4 grandkids stealing + grandpa’s money vs. 2 sons stealing is the largest amount of money that can be stolen at the current node. This is the optimal substructure in dynamic programming

Since this is a binary tree, you can optionally count all the children

• The money contributed by the four grandchildren plus the grandfather is as follows

  int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)

• The money stolen by the two sons is as follows

  int method2 = rob(root.left) + rob(root.right);

• Pick an option with more money

  int result = Math.max(method1, method2);

Write the above scheme in code as follows

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

    int money = root.val;
    
    if(root.left ! =null) {
        // The current node plus the money of the left grandchild node
        money += (rob(root.left.left) + rob(root.left.right));
    }

    if(root.right ! =null) {
        // The current node plus the money of the right grandchild node
        money += (rob(root.right.left) + rob(root.right.right));
    }

    return Math.max(money, rob(root.left) + rob(root.right));
}
Copy the code

But this way of handling time out.

Solution two, memorization – to solve the repetition sub-problem

In view of the slow speed of the solution, after analyzing its implementation, we found that when grandpa calculated how much money he could steal, he also calculated how much money his four grandchildren could steal, and how much money his two sons could steal. This creates a double-counting grandchild node when the son becomes the grandfather.

Thus we found a key optimization point for dynamic programming

Repeating subproblem

We for repeat subproblem is optimized in this step, we are doing the Fibonacci sequence, the use of optimization scheme is memory, but is to use an array to solve problems before, save every time the results of calculation, the next time you to calculate again, from the cache, no longer calculation, so as to ensure every number calculated only once.

Since binary trees are not suitable for caching arrays, we use hash tables to store results this time, TreeNode as key, and money that can be stolen as value

Solution one plus the optimized code of memory is as follows:

public int rob(TreeNode root) {
    HashMap<TreeNode, Integer> memo = new HashMap<>();
    return robInternal(root, memo);
}

public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {
    if (root == null) {
        return 0;
    }
    
    if (memo.containsKey(root)) {
        return memo.get(root);
    }
    
    int money = root.val;

    if(root.left ! =null) {
        money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
    }
    if(root.right ! =null) {
        money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
    }
    int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
    memo.put(root, result);
    return result;
}
Copy the code

At this point, some people will question the optimal substructure above. Can’t I choose one son and two grandchildren

Since the theft of the other two grandchildren has been included in the case of the other son, the maximum amount that the son can steal must be greater than the two grandchildren, so this case can be eliminated