「力扣」第 213 题：打家劫舍 II
这个问题记住就可以了。
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1：
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
分析：和 House Robber 一样，不过这次是在一个环形街道中。也就是说给定的数组中，最后一个元素和第一个元素为邻居。在不触碰警报的情况下，问能够窃取的财产的最大值是多少？
先把 198 题做一遍，然后在 198 题的基础上完成 213 题。可以利用 198 题的结论来求解。因为对于 $n$ 个房间，编号为 $0$ 到 $n-1$，我们可以将整体分为两个子序列，分别计算 $[0,…,n-2]$ 和 $[1,…,n-1]$，选取其中的最大值。
Java 代码：
import java.util.Arrays;
public class Solution {
private int tryRob(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[len - 1];
}
public int rob(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
return Math.max(tryRob(Arrays.copyOfRange(nums, 0, len - 2 + 1)),
tryRob(Arrays.copyOfRange(nums, 1, len - 1 + 1)));
}
}Python 代码：
class Solution:
def __rob_helper(self, nums):
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i % 2] = max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2])
return dp[(n - 1) % 2]
def rob(self, nums):
l = len(nums)
if l == 0:
return 0
if l <= 3:
return max(nums)
res1 = self.__rob_helper(nums[:-1])
res2 = self.__rob_helper(nums[1:])
return max(res1, res2)Python 代码：
class Solution:
def __rob_helper(self, nums):
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i % 2] = max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2])
return dp[(n - 1) % 2]
def rob(self, nums):
l = len(nums)
if l == 0:
return 0
if l <= 3:
return max(nums)
res1 = self.__rob_helper(nums[:-1])
res2 = self.__rob_helper(nums[1:])
return max(res1, res2)C++ 代码：
class Solution {
public:
int rob(vector& nums) {
int n = nums.size();
if (n < 2) return n ? nums[0] : 0;
return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
}
private:
int robber(vector& nums, int l, int r) {
int pre = 0, cur = 0;
for (int i = l; i <= r; i++) {
int temp = max(pre + nums[i], cur);
pre = cur;
cur = temp;
}
return cur;
}
}; 
