# 6/20, 入门 House Robber

## [House Robber](https://leetcode.com/problems/house-robber/)

题本身不难，Easy 难度。

先从 Top-Down 的角度来想，如果我们定义 maxProfit(n) 为长度为 n 的 array 中所能得到的最大利益的话，不难看出在计算 maxProfit(n) 的时候，它的值只和前两个 subproblem 相关，即 maxProfit(n - 1) 和 maxProfit(n - 2).

### 由此我们发现了 DP 的第一个性质： overlap subproblems.

同时如果 maxProfit(n - 1) 和 maxProfit(n - 2) 都是其对应子问题的最优解的话，我们可以只利用这两个子问题的 solution，加上对当前元素的判断，构造出 maxProfit(n) 的最优解。

### 因此我们满足了 DP 的正确性性质: optimal substructure.

### 此题的另外考点在于空间的优化。因为每一个 size = n 的问题只和前面的 2 个子问题相关，我们显然不需要存储所有的状态，而可以用滚动数组优化空间占用。 滚动数组的简单用法就是“膜” （=。=），即对 dp\[] 的 index 取 mod，

### 除数等于需要保存的状态数。

### 在数组 index % mod 的做法其实相当于做了一个 [circular buffer](https://en.wikipedia.org/wiki/Circular_buffer), 使得固定长度的数组收尾相接，依序覆盖。

### 题外话，cicular buffer 很适合用于实现 fixed-size queue，一个 java 实现看一看[这个帖子](http://www.cs.utsa.edu/~wagner/CS2213/queue/queue.html)

```java
public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);

        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++){
            dp[i % 2] = Math.max(dp[(i - 2) % 2] + nums[i], dp[(i - 1) % 2]);
        }

        return dp[(nums.length - 1) % 2];

    }
}
```

## [House Robber II](https://leetcode.com/problems/house-robber-ii/)

## 这题考察环形数组中，subproblem 的拆分与覆盖。

数组变成环形之后，就需要考虑首尾相接的问题了\~ 理论上说，对于长度为 n 的环形数组，我们现在有了 n 种不同的切分方式，去处理长度为 n 的线性数组。

### 不过我们不需要考虑所有的可能切分，因为只有相邻元素之间会出现问题。我们的 subproblem 不能再以 size = n 开始 top-down了，因为无法保证正确性； 但是 size = n - 1 的所有 subproblems，一定是正确的。我们只需要考虑，如何拆分 size = n - 1 的 subproblems，并且如何用他们构造出全局最优解。

### 只需要把环形数组拆分成两个头尾不同的 size = n - 1 的 subproblems 就可以了：

### 【1, 7, 5, 9, 2】

### 下面的 subproblem 覆盖了所有不抢最后一座房子的 subproblems；

### 【(1, 7, 5, 9) 2】

### 如下的 subproblem 覆盖了所有不抢第一座房子的 subproblems；

### 【1,(7, 5, 9, 2)】

### 如果最后的最优解第一座和最后一座房子都不抢，也一定会被包含在左右两个 subproblem 的范围内，因为其 size = n - 2;

### 【1, (7, 5, 9), 2】

### 由于我们不能同时抢第第一和最后一座房子，上面两个 overlap subproblem 一定覆盖了所有子问题的最优解，并且符合全局最优解的 optimal substructure，保证了算法的正确性。

### 易错点： 后半段数组的 index offset，合理的处置是用完全一样的 for loop，只在实际取元素的时候做 nums\[i + 1]，不然计算后半段以 i = 3 开始时，覆盖的 dp\[] 位置是错的。

```java
public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);

        int leftMax = helper(nums, 0);
        int rightMax = helper(nums, 1);

        return Math.max(leftMax, rightMax);
    }

    private int helper(int[] nums, int start){
        int max = 0;
        int[] dp = new int[2];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for(int i = 2; i < nums.length - 1; i++){
            dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i + start]);
        }

        return dp[(nums.length - 2) % 2];
    }
}
```

## [House Robber III](https://leetcode.com/problems/house-robber-iii/)

### 这题其实很像 [POJ 2342 Anniversary party ](http://blog.csdn.net/txl199106/article/details/45372337)，区别在于这里的树只有两叉，结构简单很多。

### 回顾下这章一开始对动态规划的总结，可以很容易看出来，这题的左右子树 subproblem 是 disjoint.

### 因此这道题只有 optimal substructure，而没有 overlap subproblems.

先贴一段**错误的代码**，思路就是用 level order 遍历整棵树，存下 curSum ，然后用 House Robber 一样的思路去做 DP. 错误的原因在于，不应该直接舍弃掉一层，因为层与层之间并不是 fully connected，比如\[2,1,3,null,4]，最优解是相邻两层上不相连的两个 node.

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

        List<Integer> lvlSum = new ArrayList<Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root != null) queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int curSum = 0;
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                curSum += node.val;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            lvlSum.add(curSum);
        }

        if(lvlSum.size() == 1) return lvlSum.get(0);
        if(lvlSum.size() == 2) return Math.max(lvlSum.get(0), lvlSum.get(1));

        int[] dp = new int[2];
        dp[0] = lvlSum.get(0);
        dp[1] = Math.max(lvlSum.get(0), lvlSum.get(1));

        for(int i = 2; i < lvlSum.size(); i++){
            dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + lvlSum.get(i));
        }


        return dp[(lvlSum.size() - 1) % 2];

    }
}
```

### 这道题只有 DP 的一个性质： optimal substructure，即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见，因此遇到一个问题的时候，要注意按照其性质属性仔细辨别正确解法。

### 在 Tree 上做递归的时候返回顺序已然是 bottom-up，相对于每一个节点，并没有重复计算，也没有 overlap subproblems，因此这只是一个正常的递归搜索问题，而不需要依赖 DP 进行优化。

### dfs 时间复杂度已经是 O(n) , n = # of nodes

![](/files/-MUt7aSzxAfSPnc18yjv)

```java
public class Solution {
    public int rob(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;


        int leftLvl = 0, rightLvl = 0;
        int subleftLvl = 0, subrightLvl = 0;

        if(root.left != null){
            leftLvl = rob(root.left);
            subleftLvl = rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            rightLvl = rob(root.right);
            subrightLvl = rob(root.right.left) + rob(root.right.right);
        }

        return Math.max(subleftLvl + subrightLvl + root.val, leftLvl + rightLvl);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/dong_tai_gui_hua/620-_dong_tai_gui_hua.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.