题目来源
Design a data structure that supports the following two operations:
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.
和上一道题的区别就是一个是线段，一个是环，上一个直接用dp就可以了，这个应该怎么用呢？没啥想法，看答案吧。因为我现在要快速刷题…所以想不出来就看答案。
可以通过假定i是否被抢劫来断开环。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n < 2)
return n ? nums[0] : 0;
return max(robber(nums, 0, n-2), robber(nums, 1, n-1));
}
int robber(vector<int> &nums, int l, int r)
{
int pre = 0, cur = 0;
for (int i=l; i<=r; i++) {
int tmp = cur;
cur = max(cur, pre + nums[i]);
pre = tmp;
}
return cur;
}
};
