DP-两个并列DP-HouseRobber系列

这篇是“两个并列DP”的第一篇，先写典型的HouseRobber系列。相邻的房子不能都偷(即不能2-in-a-row)。

后面再加一个paint fence，是不能有超过两个连续的（即不能3-in-a-row)。

特点是：需要分情况讨论当前的选择、

做法是：维护两个DP，维护的时候两者互相影响。

1. 偷当前元素，robCur
2. 不偷当前元素，notRobCur

题目	简介
198. House Robber
213. House Robber II
337. House Robber III
276. Paint Fence

198. House Robber

Input: [1,2,3,1] 不能偷相邻的，求最大和。Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

分情况讨论：

1. 我们决定偷当前元素：则要确定robCur[i]。

   不能偷前一个，即可以继承notRobCur[i-1]的累积收入

   当前元素可以加入累积收入，nums[i]

2. 我们决定不偷当前元素，则要确定notRobCur[i]。

   不偷当前的，于是前一个可以偷也可以不偷，但注意！！并不能将robCur[i-1]和notRobCur[i-1]加起来，因为这两者是互斥的，两个状态不能同时都要。

   比如，robCur[i-1]定义为“如果我们决定偷i-1元素的前提下，能累积收入的最大值“，和notRobCur[i-1]是条件上互斥的）

   于是，是取两种选择的max

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {return 0;}
        int len = nums.length;
        int[] robCur = new int[len];
        int[] notRobCur = new int[len];
        robCur[0] = nums[0];
        notRobCur[0] = 0;
        for (int i = 1; i < len; i++) {
            robCur[i] = notRobCur[i-1] + nums[i];//情况1
            notRobCur[i] = Math.max(robCur[i-1], notRobCur[i-1]);//情况2
        }
        return Math.max(robCur[len-1], notRobCur[len-1]);
    }
}
           

213. House Robber II

Input: [1,2,3,1] 和198.House Robber I区别在于：那个是一行，这个是排成环。Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

怎么把一行拓展到环呢？环和行区别在于：环相当于两端又增加了额外的“邻居”，需要再分两种情况讨论：

1. 偷第一个（不是非得偷第一个，而是承诺一定不偷最后一个）。于是我们就假装只存在第2到最后一个房子，[2,3,1]
2. 不偷第一个。于是我们就假装只存在第1到倒数第二个房子，[1,2,3]

然后就划归到“一行房子”的问题。

所以本题就扫两遍，取较大的结果。

另外此处我们把DP需要额外的O(n)空间减小到O(1)，比起198的码稍微优化了一点。

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {return 0;}
        else if (len == 1) {return nums[0];}
        //情况1：偷第一个（承诺不偷最后一个）
        int notRobCur = 0, robCur = 0;
        for (int i = 0; i < len - 1; i++) {
            int newRobCur = notRobCur + nums[i];
            int newNotRobCur = Math.max(robCur, notRobCur);
            robCur = newRobCur;//dp[i-1] = dp[i]
            notRobCur = newNotRobCur;
        }
        int max1 = Math.max(robCur, notRobCur);
        //情况2：承诺不偷第一个
        notRobCur = 0; robCur = 0;
        for (int i = 1; i < len; i++) {
            int newRobCur = notRobCur + nums[i];
            int newNotRobCur = Math.max(notRobCur, robCur);
            robCur = newRobCur;
            notRobCur = newNotRobCur;
        }
        int max2 = Math.max(robCur, notRobCur);
        return Math.max(max1, max2);
    }
}
           

337. House Robber III

Input: [3,2,3,null,3,null,1]

Output: 7

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

就和上面的一行和环的，本质是一样的，只是这里的邻居不是用“下标相邻”表示的，而是用tree的父子关系表示。

1. 如果偷当前节点，则它的左孩子和右孩子都是邻居，都不能偷。
2. 如果不偷当前节点，注意！不是“必须偷左右孩子”，而是“可以偷左右孩子也可以不偷” （在第三个notRobCur() 中，不是调用第二个robCur()，而是调用第一个rob())

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {return 0;}
        return Math.max(robCur(root), notRobCur(root));
    }
    private int robCur(TreeNode node) {
        if (node == null) {return 0;}
        return notRobCur(node.left) + notRobCur(node.right) + node.val;
    }
    private int notRobCur(TreeNode node) {
        if (node == null) {return 0;}
        return rob(node.left) + rob(node.right);
    }
}
           

上面是不能2-in-a-row的，下面是不能3-in-a-row的：

276. Paint Fence

Input: n = 3, k = 2 n个桩子，k种颜色可以使用，不能有超过两个桩子同色。

Output: 6

Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:

post1 post2 post3

1 c1 c1 c2

2 c1 c2 c1

3 c1 c2 c2

4 c2 c1 c1

5 c2 c1 c2

6 c2 c2 c1

这个题比house robber相比，相当于升维了，有点难想清楚。

因为规则是不能3个连到一起，于是我们要把dp[i] 和dp[i-1] 两者合并起来考虑，作为整体的状态在更新：

分两种情况：

1. 当前两个桩子同色：curTwoSame
2. 当前两个桩子不同色：curTwoDiff

在更新的时候，

当前桩子dp[i] 颜色的决策，受到前面两个桩子的影响。

（house robber只受前一个邻居影响，只考虑dp[i-1]即可）

【1】确定curTwoSame的时候，分两种情况：

1. dp[i-2]和dp[i-1]颜色相同，比如黄色

   => 则当前不能是黄色(否者违规)，然而又要求curTwoSame，就矛盾了。

   这种情况计数为0。

   应用乘法原理，0 * curTwoSame[i-1]

2. dp[i-2]和dp[i-1]颜色不同，比如蓝+黄

   => 则当前可在k种颜色中选一种。又要求curTwoSame，只能是黄色。

   这种情况计数为1。

   应用乘法原理，1 * curTwoDiff[i-1]

【2】确定curTwoDiff的时候，分两种情况：

1. dp[i-2]和dp[i-1]颜色相同，比如黄色

   => 则当前不能是黄色，可以从k-1种颜色里挑。而又要求curTwoDiff，恰好满足不是黄色。

   这种情况计数为k-1。

   应用乘法原理，(k-1) * curTwoSame[i-1]

2. dp[i-2]和dp[i-1]颜色不同，比如蓝+黄

   => 本来可以从k种颜色里挑，但又要求curTwoDiff，所以只剩k-1种。

   这种情况计数为k-1。

   应用乘法原理，(k-1) * curTwoDiff[i-1]

最后的结果，注意！和house robber不同，这里的curTwoDiff和curTwoSame是两种情况，都有可能，于是应该用“加法原理”求和；而robCur和notRobCur是互斥事件，是不能同时存在的。

（这个地方稍微有点没想清楚为啥不一样呵呵，等我变聪明了来补充）

class Solution {
    public int numWays(int n, int k) {
        if(n == 0) {return 0;}
        else if(n == 1) {return k;}
        int curTwoDiff = k * (k - 1);
        int curTwoSame = k;
        for (int i = 2; i < n; i++) {
            int preTwoDiff = curTwoDiff;
            curTwoDiff = (curTwoDiff + curTwoSame) * (k - 1);
            curTwoSame = preTwoDiff * 1;
        }
        return curTwoDiff + curTwoSame;
    }
}