LeetCode - 337. House Robber III

这道题目具有Binary Tree的结构并且拥有最优子结构这一性质，也就是说如果我们想从当前的root抢劫到最多的钱，那么我们也希望在root的left和right子树上面抢到最多的钱。题目中已经给出了rob(root)这个函数，所以目前我们需要的就是分析出如何从最优的一些子问题上构造出当前根节点的最优解，也就是怎样从rob(root.left), rob(root.right)中得到rob(root)。

由于这是个二叉树和这道题目的性质，我们自然而然想到了递归，对于递归来说，重要的是分析出它的两个性质：

1. 终结条件：当当前的树为空的时候，这时我们得到的结果是0

2. 递归关系：题目中给出了一个限制，就是二叉树中两个相邻的结点无法被同时抢劫，所以这就分成了两种情况，如果我们抢劫当前的root结点，那么得到的最大钱的数量就是当前root的val加上抢劫root的所有grandchildren结点所得到的，即root.val + rob(root.left.left) + rob(left.right) + rob(root.right.left) + rob(root.right.right)；而如果我们不抢劫当前的结点，那么得到的最大的钱的数量就是抢劫root的所有children结点所得到的钱的和，即rob(root.left) + rob(root.right)。我们要从这两种情况中选出最大值。

这种方法非常慢(1215ms)，几乎没有得到通过，代码如下：

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

        int val = 0;

        // Rob current root
        if(root.left != null){
            val += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            val += rob(root.right.left) + rob(root.right.right);
        }

        return Math.max(val + root.val, rob(root.left) + rob(root.right));
    }
}
           

我们来思考一下上面的问题，可以发现我们在计算过程中遇到了很多的重复。比如说，为了得到rob(root)，我们需要计算rob(root.left), rob(root.right), rob(root.left.left), rob(root.left.right), rob(root.right.left), rob(root.right.right)；而为了计算rob(root.left)，我们同样需要计算rob(root.left.left), rob(root.left.right)。上面的解法没有考虑这种重复，每次都进行重新计算，所以消耗了大量的时间。如果我们考虑最优子结构和重复问题(optimal substructure + overlapping of subproblems)，就是使用了动态规划的解法，一个比较方便地使用动态规划的方式就是使用一个HashMap来存储已经访问过的结点的结果，优化后的代码如下：

public class Solution {
    public int robSub(TreeNode root, Map<TreeNode, Integer> map){
        if(root == null) return 0;
        if(map.containsKey(root)) return map.get(root);
        
        int val = 0;
        
        // Do not rub current node
        if(root.left != null){
            val += robSub(root.left.left, map) + robSub(root.left.right, map);
        }
        if(root.right != null){
            val += robSub(root.right.left, map) + robSub(root.right.right, map);
        }
        
        val = Math.max(root.val + val, robSub(root.left, map) + robSub(root.right, map));
        map.put(root, val);
        
        return val;
    }
    
    public int rob(TreeNode root) {
        if(root == null) return 0;
        
        Map<TreeNode, Integer> map = new HashMap<>();
        return robSub(root, map);
    }
}
           

我们可以从另一个角度考虑这个问题，就是重复为什么产生？这是因为在rob(root)中，我们没有区分出当前root结点是否被rob的情况，所以可以说信息在向下传递的时候有了丢失。我们可以修改第一种解法来保存信息，做法就是在rob函数中使用一个数组，数组的第一个元素记录当前root结点没有被抢的结果，数组的第二个元素记录当前root结点被抢了的结果。如果当前root结点被抢，那么result = Math.max(left[0], left[1])  + Math.max(right[0], right[1])，也就是当前root结点的值加上左右子树的最大值；如果当前root结点没有被抢，那么result = root.val + left[0] + right[0]，返回这两者的最大值即可，代码如下：

public class Solution{
    public int rob(TreeNode root){
        int[] result = robSub(root);
        return Math.max(result[0], result[1]);
    }

    public int[] robSub(TreeNode root){
        if(root == null) return new int[2];

        int[] left = robSub(root.left);
        int[] right = robSub(root.right);

        int[] result = new int[2];
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
        result[1] = root.val + left[0] + right[0];

        return result;
    }
}
           

思考：

1. 这道题目非常好，分析过程也很好，非常清晰明确地体现出了由recursion到DP一步一步的思考过程，值得反复会看品味

2. DP的两个重要性质：optimal substructure + overlapping of subproblems