[LeetCode] House Robber II
House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
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.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
解题思路：
这个是偷东西的升级版。偷东西1版是一条街上一排房子，每个房子里面有金钱若干，其警报系统很怪，只有触发相邻的两个房间，警报系统才发出警报。问如何偷才能得到最大的值。
这个升级版就是这条街不再是一字排开，而是一个环形街，第一个房子与最后一个房子相邻。问如何偷才能得到最大值？
最初的想法是，记录第一个房间是否被偷了，若被偷了，那么最后一个房间就不能偷。然后分情况讨论。但是如何记录第一个房间被偷了呢？似乎比较麻烦。
其实可以有双向扫描法，第一次从左向右扫描，采用动态规划，若d[len-2]==d[len-1]，说明最后一个房间我们并没有偷，这种情况跟线性街道是一样的，返回d[len-1]即可，若不相等，说明线性街道时，最后一个房间需要偷，但是我们并不知道第一个房间是否偷了，因此我们还需要扫描一次，从左往右扫描，同样采用动态规划，得出dr[]。
此时有两个动态规划数组d[]和dr[]，注意d[]中d[len-1]!=d[len-2]。我们不知道第一间房是否偷了。假如第一间房间偷了，最后一间房不能偷，那么我们返回d[len-2]。假如第一间房没有偷，我们返回dr[1]，而不管最后一间房是否被偷。因此，我们只需要返回dr[1]和d[len-2]的较大值即可。
代码比较好懂，发现自己越解释越难懂，唉~ps，leetCode计时坏了吗？为何我的代码跑出来只需0ms？
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if(len == 0){
return 0;
}
if(len == 1){
return nums[0];
}
if(len == 2){
return max(nums[0], nums[1]);
}
int d[len];
d[0]=nums[0];
d[1]=max(nums[0], nums[1]);
for(int i=2; i<len; i++){
d[i]=max(d[i-1], nums[i]+d[i-2]);
}
if(d[len-1]==d[len-2]){ //表明最后一家没有偷，跟线性的一样
return d[len-1];
}
//反向扫描
int dr[len];
dr[len-1]=nums[len-1];
dr[len-2]=max(nums[len-1], nums[len-2]);
for(int i=len-3; i>=0; i--){
dr[i]=max(dr[i+1], nums[i]+dr[i+2]);
}
return max(dr[1], d[len-2]);
}
};
0 条评论