LeetCode 213. House Robber II

Problem

LeetCode 213. House Robber II

1. 题目简述

一个专业的抢到想要洗劫一个街区的商户，每个商户有不同数额的金钱，该街区是环形排列的（第一户和最后一户相连），当抢劫连续两个商户时，就会触发报警。问在不触发报警的情况下，如何抢劫能使获得的钱数最多，找出那个最大金额。例如：

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

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.

2. 算法思路

相关题目：

1. LeetCode 198. House Robber
2. LeetCode 337. House Robber III(待完成)
3. paint house系列（例如：LeetCode 1473. Paint House III（待完成））

动态规划

和House Robber 1（解析见动态规划一的例题）不同的是，这次首尾是相连的。也就是说如果按照1中的做法，找出来的最优解中包含了第一户和最后一户，那么这个就是一种不合法的最大值。

所以，我们的做法是如果选择了第一户，不要选择最后一户不就好了？反之亦然，所以说我们计算两个最大值，一个是从第1户到第n - 1户，另一个是从第2户到第n户，取二者的最大值即可。

我们假设F(i, j)计算的是从第i户到第j户的能够抢的最大值，那么有。

$$F(1, n) = max(F(1, n - 1), F(2, n))$$

至于F的求法，和之前一样：

$$ F(n) = Math.max(F(n - 1), F(n - 2) + nums[n]) (F(1) = nums[1], F(2) = Math.max(nums[1], nums[2])) $$

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }

        return Math.max(robFromTo(nums, 0, nums.length - 2), robFromTo(nums, 1, nums.length - 1));
    }

    private int robFromTo(int[] nums, int start, int end) {
        if (end - start == 0) {
            return nums[start];
        } else if (end - start == 1) {
            return Math.max(nums[start], nums[end]);
        }

        int pre = nums[start], cur = Math.max(nums[start], nums[]start + 1);
        for (int i = start + 2; i <= end; i++)
            int temp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = temp;
        }

        return cur;
    }
}