HouseRobberIII [source code]

public class HouseRobberIII {
static
/******************************************************************************/
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs (root);
        return Math.max (res[0], res[1]);
    }

    int[] dfs (TreeNode root) {
        if (root == null)
            return new int[]{0, 0};
        int[] left = dfs (root.left), right = dfs (root.right);
        int isPicked = root.val + left[0] + right[0], 
            isNotPicked = max (left[0] + right[0], left[0] + right[1], left[1] + right[0], left[1] + right[1]);
        return new int[] {isNotPicked, isPicked};
    }

    int max (int... nums) {
        int res = Integer.MIN_VALUE;
        for (int i : nums) if (i > res)
            res = i;
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        HouseRobberIII.Solution tester = new HouseRobberIII.Solution();
    }
}

最后还算是有惊无险的做出来了; 首先是一个有subproblem性质的tree问题, 这个还是比较好发现的; 那么我们很自然的想要定义一个有root involvement的返回值; 这里最后定义的是要返回两个值, 一个是max if root is NOT picked, 另外一个是max if picked. 这样一个定义应该是很熟练的了;

不过这题的一个小的subtlety就是, isNotPicked and isPicked的计算方式之间有所差别; isPicked就很好计算, 但是isNotPicked的话, 需要有一个最值操作: 当前root不被pick, 不代表你就一定必须要pick你的direct child;

最后的速度是3ms (49%), 可以接受;

2018-04-22 22:08:53 准备谷歌电面的时候回头看这个题目; 有人说这个题目当时要求一个DP解法; 想不通是什么意思; 但是看了下面的discuss的解法, 好像大概有印象了, 知道这个所谓的DP是什么意思;

他的naive解法就是直接往底下查询; 我的这个解法实际上已经是DP了; 每一个node只访问一次, Bottom-Up上行的时候所有有用的结果都返回上来, 相当于一个N*2维度的DP表格的填表过程;

没有editorial;

discussion最优解, 非常长, 其实最后得到的最有版本的解法跟我的解法是一样的:

@fun4LeetCode said in Step by step tackling of the problem:

Step I -- Think naively

At first glance, the problem exhibits the feature of "optimal substructure": if we want to rob maximum amount of money from current binary tree (rooted at root), we surely hope that we can do the same to its left and right subtrees.

So going along this line, let's define the function rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at root; the key now is to construct the solution to the original problem from solutions to its subproblems, i.e., how to get rob(root) from rob(root.left), rob(root.right), ... etc.

Apparently the analyses above suggest a recursive solution. And for recursion, it's always worthwhile figuring out the following two properties:

  1. Termination condition: when do we know the answer to rob(root) without any calculation? Of course when the tree is empty -- we've got nothing to rob so the amount of money is zero.

  2. Recurrence relation: i.e., how to get rob(root) from rob(root.left), rob(root.right), ... etc. From the point of view of the tree root, there are only two scenarios at the end: root is robbed or is not. If it is, due to the constraint that "we cannot rob any two directly-linked houses", the next level of subtrees that are available would be the four "grandchild-subtrees" (root.left.left, root.left.right, root.right.left, root.right.right). However if root is not robbed, the next level of available subtrees would just be the two "child-subtrees" (root.left, root.right). We only need to choose the scenario which yields the larger amount of money.

Here is the program for the ideas above: 

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

        int val = 0;  

        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));  
    }

However the solution runs very slowly (1186 ms) and barely got accepted (the time complexity turns out to be exponential, see my comments below).

Step II -- Think one step further

In step I, we only considered the aspect of "optimal substructure", but think little about the possibilities of overlapping of the subproblems. For example, to obtain rob(root), we need rob(root.left), rob(root.right), rob(root.left.left), rob(root.left.right), rob(root.right.left), rob(root.right.right); but to get rob(root.left), we also need rob(root.left.left), rob(root.left.right), similarly for rob(root.right). The naive solution above computed these subproblems repeatedly, which resulted in bad time performance. Now if you recall the two conditions for dynamic programming: "optimal substructure" + "overlapping of subproblems", we actually have a DP problem. A naive way to implement DP here is to use a hash map to record the results for visited subtrees.

And here is the improved solution: 

    public int rob(TreeNode root) {  
        return robSub(root, new HashMap<>());  
    }  

    private int robSub(TreeNode root, Map<TreeNode, Integer> map) {  
        if (root == null) return 0;  
        if (map.containsKey(root)) return map.get(root);  

        int val = 0;  

        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(val + root.val, robSub(root.left, map) + robSub(root.right, map));  
        map.put(root, val);  

        return val;  
    }

The runtime is sharply reduced to 9 ms, at the expense of O(n) space cost (n is the total number of nodes; stack cost for recursion is not counted).

Step III -- Think one step back

In step I, we defined our problem as rob(root), which will yield the maximum amount of money that can be robbed of the binary tree rooted at root. This leads to the DP problem summarized in step II.

Now let's take one step back and ask why we have overlapping subproblems. If you trace all the way back to the beginning, you'll find the answer lies in the way how we have defined rob(root). As I mentioned, for each tree root, there are two scenarios: it is robbed or is not. rob(root) does not distinguish between these two cases, so "information is lost as the recursion goes deeper and deeper", which results in repeated subproblems.

If we were able to maintain the information about the two scenarios for each tree root, let's see how it plays out. Redefine rob(root) as a new function which will return an array of two elements, the first element of which denotes the maximum amount of money that can be robbed if root is not robbed, while the second element signifies the maximum amount of money robbed if it is robbed.

Let's relate rob(root) to rob(root.left) and rob(root.right)..., etc. For the 1st element of rob(root), we only need to sum up the larger elements of rob(root.left) and rob(root.right), respectively, since root is not robbed and we are free to rob its left and right subtrees. For the 2nd element of rob(root), however, we only need to add up the 1st elements of rob(root.left) and rob(root.right), respectively, plus the value robbed from root itself, since in this case it's guaranteed that we cannot rob the nodes of root.left and root.right.

As you can see, by keeping track of the information of both scenarios, we decoupled the subproblems and the solution essentially boiled down to a greedy one. Here is the program: 

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

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

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

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);  
        res[1] = root.val + left[0] + right[0];  

        return res;  
    }

大概的意思并不复杂; 但是我自己还是有必要给自己来一发总结; 首先, 前面我忘记提到了这个问题其实我是意识到是一个DP问题的; 我只不过想到直接解决; 只要我们最后定义的返回值符合subproblem性质, 那么就不用担心recursion当中的repeated call. 而且只要表格定义好了, 那么就可以直接Bottom-Up的方式走一遍就行了; 这个也是我拿到题目之后立刻就开始做的工作;

然后我自己前面总结的时候也提到一个概念就是root involvement, 这个东西其实就相当于我刚开始学DP的时候一直强调的DP decision的概念; 如果用child level的思路去思考, 那么这个decision就是你在每一个level要进行的一个抉择; 这样一个involvement往往构成DP表格的另外一个维度, 也就对应了表格的另外一个index.

当然, 因为这题是一个tree问题, 所以实际上并没有explicit的表格概念, 但是index还是有的, 分别是每一个call的root, 和decision对应的一个长度为2的dimension;

这样以后, 最后再设计好root level decision的实现方式, 这个算法基本就算是成型了;

另外, 他最后这个版本[0]的计算其实比我的简练; 这里的关键是, 左右两个subtree之间是独立的, 所以只要左右分别选择各自的最大值就行了;

这个是下面一个有意思的改写:

@ofLucas said in Step by step tackling of the problem:

here's another way of solution, I have a little different definition of DP, so:

maxMoney[0] = max Money avoiding root itself

maxMoney[1] = max Money allowing root to be stolen

the transfer equation can be read as below: 

    public class Solution {  
        public int rob(TreeNode root) {  
            return maxMoney(root)[1];  
        }  

        // return int[2]: maxMoney[0] = max Money avoiding root itself, maxMoney[1] = max Money allowing root to be stolen  
        private int[] maxMoney(TreeNode root) {  
            if (root == null) return new int[2];  
            int[] ans = new int[2],   
                    l = maxMoney(root.left),   
                    r = maxMoney(root.right);  
            ans[0] = l[1] + r[1];  
            ans[1] = Math.max(root.val + l[0] + r[0], ans[0]);  
            return ans;  
        }  
    }

注意看他这里的定义, 他的[0]还是一样的, 但是他的[1]的定义是包含[0]的定义, 所以体现了一个allow, 或者说maybe的概念; 这样一个定义让最后root level decision写起来方便很多;

当然, 这个定义本身并不如直接的pick or not pick那么intuitive, 但是可以适当了解一下; 不知道怎么掌握.

后面想起来, 可以这样理解, 假如你就是有一个[N][2]的表格, 你现在Bottom-Up填表, 你希望怎么填? 即使是在同一个row上面, 其实也可以允许一定的包含关系. 不过这个其实还并不是一个很guide性质的理解, 只能尝试性的理解到这样;

submission最优解: 1(75): 

class Solution {  
    public int rob(TreeNode root) {  
        if (root == null) return 0;  
        int[] result = help(root); //return int[]{with root, without root}  
        return Math.max(result[0], result[1]);  
    }  

    private int[] help(TreeNode root) {  
        if (root == null) {  
            return new int[]{0, 0};  
        }  
        int[] left = help(root.left);  
        int[] right = help(root.right);  
        //with root  
        int with = root.val + left[1] + right[1];  
        int without = left[0] + right[0];  
        with = Math.max(with, without);  
        int[] result = new int[]{with, without};  
        return result;  
    }  

}

差不多的, 这个好像是那个contains结构的写法;

Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1: 

     3  
    / \  
   2   3  
    \   \   
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2: 

     3  
    / \  
   4   5  
  / \   \   
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Credits:

  • Special thanks to @dietpepsi for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:57.2K
Total Submissions:129K
Contributor:LeetCode
Companies
uber
Related Topics
treedepth-first search
Similar Questions
House Robber

results matching ""

    No results matching ""