目录
一、题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例?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 = [1,2,3]
输出：3
二、运行结果
?
三、解题思路
这里和“”打家劫舍”I的唯一区别就是第一家和最后一家不能同时偷，打家劫舍I是从第一家到最后一家进行动态规划，那么这题可以分为两次动态规划（可以在一次遍历中完成）：
1）从第一家偷到倒数第二家，在这个范围内进行动态规划迭代计算；
2）从第二家偷到最后一家，在这个范围内进行动态规划迭代结算；
两种偷法中能偷到的最大值就是所求。
打家劫舍I的具体做法可以参考我的另一篇博客：打家劫舍-力扣198-Java动态规划_TLJava^v^的博客-CSDN博客
这里的解法进行了空间优化，因为每次计算当前最大值置用到了前面两个位置的统计结果，所以不需要用整个数组进行存储。?
四、代码
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len == 0) return 0;
else if(len == 1) return nums[0];
int pre1=0, cur1=nums[0], tmp1;//存储从第一家开始偷的统计量
int pre2=0, cur2=0, tmp2; //存储从第二家开始偷的统计量（可偷最后一家）
for(int i=1; i<len-1; ++i){
tmp1 = cur1;
cur1 = Math.max(pre1+nums[i], cur1);
pre1 = tmp1;
tmp2 = cur2;
cur2 = Math.max(pre2+nums[i], cur2);
pre2 = tmp2;
}
cur2 = Math.max(pre2+nums[len-1], cur2); //看偷最后一家能否增加
return Math.max(cur1, cur2);
}
}