你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例1 ：
1
2
3
| 输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
|
示例2：
1
2
3
4
| 输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
|
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
本题是198. 打家劫舍的升级题目，难点在于环状结构，不能同时偷取首尾两家。当前收益最大有两种情况，第一种情况是前一家偷过了，那么当前最大收益就是前一天的最大收益，第二种情况是前一家没有偷过，那么当前的最大收益就是前前天的最大收益，加上当前能偷得钱的金额。
同时边界条件为dp[0] = nums[0],dp[1] = Math.max(nums[0], nums[1])，我们写出状态转移方程：
解这道题有个取巧的方式就是将一个数组分为两个子数组，一个子数组为nums[0, nums.length - 1]，另一个子数组为nums[1, nums.length - 1]，分别求取两个子数组的最大收益，然后返回最大值即可。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public int rob(int[] nums) {
if (nums.length == 0 || nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2){
return Math.max(nums[0], nums[1]);
}
int result1 = 0, result2 = 0;
int dp0 = nums[0];
int dp1 = Math.max(nums[0], nums[1]);
int dp2 = Math.max(dp0, dp1);
for (int i = 2; i < nums.length - 1; i++) {
dp2 = Math.max(dp1, dp0 + nums[i]);
dp0 = dp1;
dp1 = dp2;
}
result1 = dp2;
dp0 = nums[1];
dp1 = Math.max(nums[1], nums[2]);
dp2 = Math.max(dp0, dp1);
for (int i = 3; i < nums.length; i++) {
dp2 = Math.max(dp1, dp0 + nums[i]);
dp0 = dp1;
dp1 = dp2;
}
result2 = dp2;
return Math.max(result1, result2);
}
}
|
