213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [0]
输出：0
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
解题思路
方法一： 动态规划
和 Medium | LeetCode 198. 打家劫舍 | 动态规划 类似。不过加了一个条件, 前一道题是线型的, 这一道题是环形的。区别在于环形的最后一个数字和数组的第一个数字不能同时偷。
直接分类讨论, 分两种情况讨论。
第一种情况是第一个偷, 把第一个写死。
第二种情况是第一个不偷, 把第一个写死。
针对这两种情况, 使用与前面一道题的动态规划迭代方法。一直迭代到倒数第二个元素。
在迭代倒数第一个元素, 也是返回结果时。有两种可能性, 从这两种可能性取最大值返回即可。
最后一个不偷, 那么返回值就是上面的第一个偷, 第一个不偷 这两种策略一直迭代到倒数第二个元素的值的较大者。
最后一个偷, 那么返回值是 第一个不偷+最后一个偷。
对以上两种情况取最大值返回即可。
public int rob(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
if (len == 2) {
return Math.max(nums[0], nums[1]);
}
// 设置两个数组, 分别表示第一个偷与不偷, 在两个数组里, 第一个值直接写死
int[] firstRub = new int[len];
firstRub[0] = nums[0];firstRub[1] = nums[0];
int[] firstUnRub = new int[len];
firstUnRub[1] = nums[1];
// 动态规划向前迭代
for (int i = 2; i < len - 1; i++) {
firstRub[i] = Math.max(firstRub[i-1], firstRub[i-2] + nums[i]);
firstUnRub[i] = Math.max(firstUnRub[i-1], firstUnRub[i-2] + nums[i]);
}
return Math.max(
Math.max(firstRub[len-2], firstUnRub[len-2]), // 最后一个不偷
firstUnRub[len-3] + nums[len-1]); // 最后一个偷
}
方法二： 动态规划 + 滚动数组
方法一借助了两个辅助DP数组, 用于标识两种策略下偷到第i个物品的总价值。时间复杂度是O(N)。这其实可以通过滚动来实现。
下面的代码的空间复杂度是O(1)
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
// 设置两个数组, 分别表示第一个偷与不偷, 在两个数组里, 第一个值直接写死
int grandPre1 = nums[0], pre1 = nums[0];
int grandPre2 = 0, pre2 = nums[1];
int cur1 = 0, cur2 = 0;
// 动态规划向前迭代
for (int i = 2; i < nums.length - 1; i++) {
cur1 = Math.max(pre1, grandPre1 + nums[i]);
grandPre1 = pre1;
pre1 = cur1;
cur2 = Math.max(pre2, grandPre2 + nums[i]);
grandPre2 = pre2;
pre2 = cur2;
}
return Math.max(
Math.max(pre1, pre2), // 最后一个不偷
grandPre2 + nums[nums.length - 1] // 最后一个偷
);
}
除此之外, 还有一种更加简洁的写法, 如下
直接按照第一个是否偷的原则, 讲一个数组拆分成两份。分别在两个数组内求结果返回其中的较大者。
public int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
myRob(Arrays.copyOfRange(nums, 1, nums.length)));
}
private int myRob(int[] nums) {
int pre = 0, cur = 0, tmp;
for(int num : nums) {
tmp = cur;
cur = Math.max(pre + num, cur);
pre = tmp;
}
return cur;
}