05 August 2008
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
1
2
3
4
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
1
2
3
4
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
跟上一题198唯一的区别是此题中的房间是环状排列的（即首尾相接），而这也是此题的难点。
环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃, 比如说输入数组 nums=[2,3,2]，算法返回的结果应该是 3 而不是 4，因为开头和结尾不能同时被抢。首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢。
这三种情况，那种的结果最大，就是最终答案，不过，其实不需要比较三种情况，只要比较情况二和情况三就行了，因为这两种情况对于房子的选择余地比情况一大呀，房子里的钱数都是非负数，所以选择余地大，最优决策结果肯定不会小
综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1, p2) 。
1) 状态定义 - dp[i]表示第i个元素的最大值（从1开始），也就是有多少个房子时候的最大值
2) 初始化 - dp[0] 没有房子，dp[1] 一个房子
3) 递推式，在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的 dp 数组。写出递推方程 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) - i - 1是当前元素
4） 考虑状态压缩，dp[n] 只与 dp[n−1] 和 dp[n−2] 有关系，因此可以设两个变量 cur和 pre 交替记录，将空间复杂度降到 O(1)。
时间复杂度O(N)， 空间复杂度O(1)。
DP
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
class Solution {
// dp[i] 到index为i的时候的最大值
// dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
// 把数组分成两种情况，只抢[1：len]和[0：len-1]，比较谁更大
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
if (len == 1) {
return nums[0];
}
if (len == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(rob(nums, 0, len - 1), rob(nums, 1, len));
}
private int rob(int[] nums, int start, int end) {
int[] dp = new int[nums.length];
dp[start] = nums[start]; // 注意在数组中的起点
dp[start + 1] = Math.max(nums[start], nums[start + 1]); // 注意在数组中的起点
for (int i = start + 2; i < end; i++) { // 注意在数组中的起点
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end - 1];
}
}
状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
}
// 0..len-2表示最后一个房子不抢，len-1是最后一个房子
// 1..len-1表示第一个房子不抢，0是第一个房子
return Math.max(robRange(nums, 0, len - 2), robRange(nums, 1, len - 1));
}
private int robRange(int[] nums, int start, int end) {//[start, end]
int dp_i_1 = 0, dp_i_2 = 0; //分别表示临近的状态和隔一个房间的状态
int max = 0; // 记录最大值
for (int i = end; i >= start; i--) {
max = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = max;
}
return max;
}
}