1.剑指Offer II 89
题目要求
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
题目分析
题目的意思很简单：给出一个一维数组，因为相邻的数不能相加，那也就意味着我们对下标为偶数的，和奇数的数组分别进行求和，然后取最大值也就是我们的最终结果。
解题代码
class Solution {
public int rob(int[] nums) {
int length = nums.length;
//先判空
if(nums == null || length == 0){
return 0;
}
//若是只有一个元素则返回第一个即可；
if(length == 1){
return nums[0];
}
//创建dp数组，找到递推式
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[length-1];
}
}
我们的解题思路是使用动态规划，上述代码中先将边界情况进行处理，然后创建dp数组保存一定数量房子可以偷盗的最大价值；最后返回最后一项即可；
但是每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，所以我们可以用滚动数组，节省不必要的空间；
class Solution {
public int rob(int[] nums) {
int length = nums.length;
//先判空
if(nums == null || length == 0){
return 0;
}
//若是只有一个元素则返回第一个即可；
if(length == 1){
return nums[0];
}
//创建dp数组，找到递推式
int first = nums[0],second = Math.max(nums[0],nums[1]);
for(int i=2;i<length;i++){
int temp = second;
second = Math.max(first+nums[i],second);
first = temp;
}
return second;
}
}
2.剑指Offer II 90 环形房屋偷盗
一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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 <= 100
0 <= nums[i] <= 1000
分析
该题其实是在89房屋偷盗问题上加了一点限制，让头和尾变成相邻的了，也就是说有头就没有尾，反之一样。所以我们可以将该数组分成两部分，每部分按照89题求解思路解决，然后将两部分的返回值进行取最大值即可。
解题代码
class Solution {
public int rob(int[] nums) {
if(nums.length == 1){
return nums[0];
}else if(nums.length==2){
//两个元素那一定是相邻的，所以取最大值即可
return Math.max(nums[0],nums[1]);
}
return Math.max(maxMoney(nums,0,nums.length-2),maxMoney(nums,1,nums.length-1));
}
//同89题
public static int maxMoney(int[] nums,int start,int end){
int first = nums[start],second = Math.max(nums[start],nums[start+1]);
for(int i=start+2;i<=end;i++){
int temp = second;
second = Math.max(first+nums[i],second);
first = temp;
}
return second;
}
}
