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

分析

第一个版本的House Robber是从一个序列中选择一些元素，使得和最大，但不能选择相邻的元素，这里的情况基本一样，只不过加了一个条件，根据题目描述，第一个房间和最后一个房间是相邻的，也就是说抢了第一家，就不能抢最后一家，不抢第一家，抢第二家，就可以抢最后一家。也就是分两种情况，第一种情况是从第一家到倒数第二家的最大值，第二种情况是从第二家到最后一家的最大值。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(0 == n) {
            return 0;
        }
        if(1 == n) {
            return nums[0];
        }
        
        vector<int> maxv(n, 0);
        maxv[0] = nums[0];
        maxv[1] = max(nums[0], nums[1]);    
        for(int i = 2; i < n-1; i++) {
            maxv[i] = max(maxv[i-2] + nums[i], maxv[i-1]);
        }
        int result1 = maxv[n-2];
        
        maxv[1] = nums[1];
        maxv[2] = max(maxv[1], nums[2]);
        for(int i = 3; i < n; i++) {
            maxv[i] = max(maxv[i-2] + nums[i], maxv[i-1]);
        }
        return max(result1, maxv[n-1]);
    }
};

相关问题

(E) Paint Fence
(E) House Robber
(M) Paint House
(M) House Robber III

题目来源