leetcode 213. House Robber II

青旅半醒 2022-07-28 01:12 147阅读 0赞

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.

class Solution {
    	void do_once(map<int, int>&candi, int& max, vector<int>&nums, int end)
    	{
    		map<int, int>newcandi;
    		for (map<int, int>::iterator it = candi.begin(); it != candi.end(); it++)
    		{
    			if (it->first == end)
    			{
    				if (it->second > max)
    					max = it->second;
    				continue;
    			}
    			if (it->first + 2 < end)
    			{
    				if (newcandi.find(it->first + 2) == newcandi.end())
    					newcandi[it->first + 2] = it->second + nums[it->first];
    				else
    				{
    					if (it->second + nums[it->first] > newcandi[it->first + 2])
    						newcandi[it->first + 2] = it->second + nums[it->first];
    				}
    			}
    			else
    			{
    				if (it->second + nums[it->first] > max)
    					max = it->second + nums[it->first];
    			}
    			if (it->first + 1 == end)
    			{
    				if (it->second + nums[it->first] > max)
    					max = it->second + nums[it->first];
    				continue;
    			}
    			if (it->first + 3 < end)
    			{
    				if (newcandi.find(it->first + 3) == newcandi.end())
    					newcandi[it->first + 3] = it->second + nums[it->first + 1];
    				else
    				{
    					if (it->second + nums[it->first + 1] > newcandi[it->first + 3])
    						newcandi[it->first + 3] = it->second + nums[it->first + 1];
    				}
    			}
    			else
    			{
    				if (it->first + 1 < end && it->second + nums[it->first + 1] > max)
    					max = it->second + nums[it->first + 1];
    			}
    		}
    		candi = newcandi;
    	}
    public:
    	int rob(vector<int>& nums) {
    		if (nums.empty())
    			return 0;
    		if (nums.size() == 1)
    			return nums[0];
    		if (nums.size() == 2)
    			return nums[0] > nums[1] ? nums[0] : nums[1];
    
    		map<int, int>candi;//<int,int>(index,sum)  
    		candi.insert(pair<int, int>(2, nums[0]));
    		int max = 0;
    		while (!candi.empty())
    		{
    			do_once(candi, max, nums, nums.size() - 1);
    		}
    		
    		candi.insert(pair<int, int>(3, nums[1]));
    		while (!candi.empty())
    		{
    			do_once(candi, max, nums, nums.size());
    		}
    		if (nums.size() > 4)
    		{
    			candi.insert(pair<int, int>(4, nums[2]));
    			while (!candi.empty())
    			{
    				do_once(candi, max, nums, nums.size());
    			}
    		}
    		return max;
    	}
    };

accepted