> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/dong_tai_gui_hua/620-_dong_tai_gui_hua.md).

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