1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[dp.length - 1];
    }
}

这是我的第一种写法. 其实刚开始没看懂题, 以为一个间隔一个抢就行了, 但这样的问题就是比如[2 1 1 2]. 如果我们间隔抢只能抢到3, 但是只抢2和2就能拿到4, 也就是可以跳多个不抢. 因此这让我开始思考DP. 对于前n个房子, 我如果我能知道抢第n - 1个房子, 那么前n个最大就是和抢前n - 1个房子的最大值一样了. 如果不抢第n - 1个房子, 那么抢前n个房子的最大就是前n - 2的最大 + nums[i]了. 我们知道不抢n - 1个房子就是抢前n - 2个房子能够得到的最大即可. 那抢第n - 1个房子的最大如何知道呢? 这是个问题了. 因此这个思路不是很好. 我们干脆直接算前n个房子能够抢到的最大. 那么如果想知道前n个, 我们就需要知道前n - 1个房子能抢到的最大. 那么还是这个问题: 前n - 1个房子抢最多包不包括抢nums[n - 1]呢? 如果包括, 那么就不能抢nums[n]了, 如果不包括就能抢nums[n]了. 如果不包括还好说, 表示前n - 1个房子最多能抢这么多, 那么前n个呢带上nums[n]就行了. 如果包括nums[n - 1], 我们要思考了, 前n个房子抢的话此时带不上nums[n], 那么这样一定能保证抢到最多吗? 如果有某种路线不带nums[n - 1]而带nums[n]能否抢到更多呢? 这种情况是有的. 比如[1, 100, 500]. 我们想知道前三个房子能抢的最大值, 我们看前两个, 前两个很容易得到是只抢第2个, 此时的情况就是抢前两个房子的时候是抢第二个房子的. 那么此时我们就会发现如果抢第一个和第三个会比只抢第二个要能抢到更多. 综上我们还要考虑前n - 1个房子没有nums[n - 1]出现的时候的最大值是多少. 这不就是前n - 2个房子能抢的最多值吗? 前n - 2个房子能抢的最多值肯定不包含nums[n - 1], 此时这个值加上nums[i]和抢前n - 1个房子能得到最大的值比较, 大的那个就是抢前n个房子的最大值了. 前n - 1能抢到的最大值可能包含nums[n - 1]可能不包含, 不管包不包含, 我们都让它和dp[n - 2] + nums[i]比较. 如果包含, 那么正合我们心意, 比较这两个; 如果不包含, 那么这个比较也没坏处. 等于是这个比较把包含nums[n - 1]的情况给考虑进去, 即使我们dp[n - 1]的抢劫方案不包含nums[n - 1], 这样的比较也不会影响什么.

其实如果前n - 1个最大不包含nums[n - 1], 抢前n - 2个房子的最大值的抢劫方案和抢前n - 1个房子的抢劫方案相同. 比如: [100, 1, 200]. 此时抢前1个就是100, 抢前两个还是100. 等于是抢前n - 1个房子得到最大值的方案可能包含nums[n - 1]可能不包含. 正是我们不知道包不包含, 我们才要看前n - 2个抢的最大值. 如果不包含, 那么前n - 1和前n - 2个抢劫的方案是一样的, 我们比较前n - 1个房子抢的最大值和前n - 2个抢的最大值 + nums[n]肯定是后者更大, 只是此时前者+ nums[i]也可以取到最大, 只是我们不知道此时不包含nums[n - 1]. 如果包含nums[n - 1]那么两种情况截然不同, 于是我们需要进行比较, 看是前n - 1的大, 还是前n - 2的 + nums[n]大. 不管哪一种情况, 我们通过这个比较最终都会得到正确的dp[n].

dp[n]的定义是从0到n(inclusive)的房子能抢到的最大值. 我一开始的定义是不对的, 我之前定义是dp[n]表示从0到n(inclusive)的房子能抢到的最大值并且抢的
方案中一定会包含抢第n个房子. 然而此时的情况如果还是套用那个dp公式, 得到的结果就是前n - 2个房子包含nums[n - 2]的前提下的最大, 同理前n - 1个房子包含nums[n - 1]的前提下最大. 然而有可能前n - 1个最大是在不抢nums[n - 1]时达到的. 同理前n - 2个最大也可能不抢nums[n - 2]. 我们武断地判定抢到最大就要一定包含第n - 2个元素或者第n - 1个元素, 这是不对的. [2, 1, 1, 2]就是个范例. 前四个房子抢到最大不一定要包含第三个房子或第二个房子, 只抢第一个房子的时候才能抢到最多. 因此正确的dp定义就是前n个房子能抢到的最多, 不管包不包含抢第n个房子.

时间复杂度: O(n)
空间复杂度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int one = nums[0];
        int two = nums[0] > nums[1] ? nums[0] : nums[1];
        for (int i = 2; i < nums.length; i++) {
            int temp = Math.max(two, one + nums[i]);
            one = two;
            two = temp;
        }
        return two;
    }
}

我们还可以继续优化, 因为dp[n]只需要知道dp[n - 1]和dp[n - 2]的值就行, 那么我们用两个变量来存储这两个位置的值, 不停地更新这两个变量即可. 有点儿类似斐波那契数列了.

此时时间复杂度不变, 空间复杂度变为O(1)

至于递归的解法是一样的思路, 看前n - 1个房子抢的情况和前n - 2个房子抢的情况 + nums[i]哪个大即可. 问题在于意识到前n - 1个房子抢到最大的方案可能包含nums[n - 1], 可能不包含, 此时会可能出现某个方案使得不包含nums[n - 1]但包含nums[n]的情况让抢的东西达到最多, 于是我们要看前n - 2个房子能抢到最大是多少. 也就是前n - 1个最大可能包含抢nums[n - 1], 也可能不包含, 此时为了考虑不包含的情况, 我们看一下前n - 2个最大是多少. 因为如果包含nums[n - 1], 前n - 1个最大就是我们要的. 如果不包含, 前n - 1个最大不是我们要的答案, 我们要看前n - 2最大 + nums[n].