【Leetcode】213. House Robber II（环形抢劫问题）

墨蓝 2022-01-27 05:07 182阅读 0赞

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

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

**Example 1:**

Input: [2,3,2]
    Output: 3
    Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
                 because they are adjacent houses.

**Example 2:**

Input: [1,2,3,1]
    Output: 4
    Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
                 Total amount you can rob = 1 + 3 = 4.

题目大意：

是[198题][198]的拓展

将原有的链式结构，变成了环形结构，此时连续的两个房子不能够被抢劫。

解题思路：

我们发现与原先不同之处在于，如果第一个位置被抢劫则最后一个位置不可能被抢，若最后结果中最后一个位置被包含在内，则我们需要从第二个位置开始DP这个数组，不管第二个位置是否是必须的。

所以分两种情况最后选择最大值即可。

class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if(n==0) return 0;
            if(n==1) return nums[0];
            if(n==2) return max(nums[0], nums[1]);
            if(n==3) return max(nums[0], max(nums[1], nums[2]));
            int ans_1 = nums[0];
            vector<int> tmp(nums.begin(), nums.end());
            for(int i=2; i<nums.size()-1; i++){
                if(i==2){
                    tmp[i] += tmp[i-2];
                }else{
                    tmp[i] += max(tmp[i-2], tmp[i-3]);
                }
                ans_1 = max(ans_1, tmp[i]);
            }
            int ans_2 = nums[1];
            vector<int> tmp_new(nums.begin(), nums.end());
            for(int i=3; i<nums.size(); i++){
                if(i==3){
                    tmp_new[i] += tmp_new[i-2];
                }else{
                    tmp_new[i] += max(tmp_new[i-2], tmp_new[i-3]);
                }
                ans_2 = max(ans_2, tmp_new[i]);
            }
            return max(ans_1, ans_2);
        }
    };

[198]: https://blog.csdn.net/qq_29600137/article/details/90238755