leetCode 213. House Robber II | Medium | Dynamic Programming

213. 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.

題目大意：

此題是 198. House Robber 的升級(jí)版。之前已經(jīng)做過。鏈接如下：

http://qiaopeng688.blog.51cto.com/3572484/1844956

第一版的房間形成的街道是一條直線。

第二版的房間形成的街道是成一個(gè)圓。

思路：

因?yàn)閳A的首尾是相鄰的，所以選首不能選尾，選尾不能選首。所以有了下面的思路。

1. 求出不選尾的最大值。也就是數(shù)組中a[0]到a[N-1]求出最大值。

2. 求出不選首的最大值。也就是數(shù)組中a[1]到a[N]求出最大值。

3. 比較1，2的最大值，然后得到最終結(jié)果。

代碼如下：

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int numLength = nums.size();
    	if (nums.empty())
    		return 0;
    	if (1 == numLength)
    		return nums[0];
    	if (2 == numLength)
    		return nums[0] > nums[1] ? nums[0] : nums[1];
    	int *maxV1 = new int[nums.size() - 1];// 0---nums.size()-2
    	int *maxV2 = new int[nums.size() - 1];// 1---nums.size()-1
    	int result = 0;
    	maxV1[0] = nums[0];
    	maxV1[1] = nums[0] > nums[1] ? nums[0] : nums[1];
    
    	for (int i = 2; i < nums.size() - 1; ++i)
    	{
    		maxV1[i] = max(maxV1[i - 2] + nums[i], maxV1[i - 1]);
    	}
    
    	maxV2[0] = nums[1];
    	maxV2[1] = nums[1] > nums[2] ? nums[1] : nums[2];
    	for (int i = 3; i < nums.size(); ++i)
    	{
    		maxV2[i - 1] = max(maxV2[i - 3] + nums[i], maxV2[i - 2]);
    	}
    
    	result = max(maxV1[nums.size() - 2], maxV2[nums.size() - 2]);
    
    	delete maxV1;
    	delete maxV2;
    	maxV1 = NULL;
    	maxV2 = NULL;
    	return result;
    }
};

總結(jié)：

代碼瞬息萬變，解決萬千問題。哈哈哈哈。有意思。

2016-08-31 23:41:18