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.
解析：与之前题目条件相同，加了一个条件是街道是环形，这样第一家与最后一家就不能同时偷，这样的话分两种情况，求第一家到倒数第二家的最大值与第二家到最后一家的最大值，求两者的最大值即可。
代码：
class Solution { public: int rob(vector<int>& nums) { if (nums.empty()) return 0; if (nums.size()==1) return nums[0]; vector<int>dp(nums.size(),0); dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]); for (int i=2; i<nums.size()-1; i++) { dp[i]=max(dp[i-2]+nums[i],dp[i-1]); } int res=dp[nums.size()-2]; dp[1]=nums[1]; dp[2]=max(nums[1],nums[2]); for (int i=3; i<nums.size(); i++) { dp[i]=max(dp[i-2]+nums[i],dp[i-1]); } return max(res,dp[nums.size()-1]); } };
