题目：
213. House Robber II(medium)
解题思路：
这个题是leetcode198那个题的升级版，在不能盗窃相邻房屋的约束上，多加了一条：最后一个房屋和第一个房屋也是紧挨着的，所以也不能同时盗窃。所以，盗窃范围有两个可选范围：编号0到n-2号，编号1到n-1号。这两个过程互不影响，应该取其中结果更大的，取个max。单个过程就是典型的dp的过程，状态转移方程还是：dp[i] = max(dp[i-2]+nums[i],dp[i-1]),dp[i]为抢劫到第i个房屋时的最大收益
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17Java:
public int rob(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int n = nums.length;
if(n == 1) return nums[0];
return Math.max(rob(nums,0,n-2),rob(nums,1,n-1));
}
private int rob(int[] nums,int first,int last){
int pre2 = 0,pre1 = 0;
for(int i = first;i <= last;++i){
int cur = Math.max(pre1,pre2+nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
