leetcode House Robber II

小鱼儿 2022-08-01 11:08 137阅读 0赞

# 题目 #

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.

题目来源：[https://leetcode.com/problems/house-robber-ii/][https_leetcode.com_problems_house-robber-ii]

# 分析 #

上一个题house robber的解析见：[http://blog.csdn.net/u010902721/article/details/46583815][http_blog.csdn.net_u010902721_article_details_46583815]

这个题在上一道题的基础上加了一个限制条件，也就是首和尾也是相邻的。那就拆开做，分别去掉第一个元素和最后一个元素后再用第一道题的方案去求解。最大值就是本题的答案。

# 代码 #

class Solution {
    public:
        int rob1(vector<int>& nums, int begin, int end) {
            int size = end - begin + 1;
            if(size == 1)
                return nums[begin];
            vector<int> dp(size + 1, 0);
            dp[size-1] = nums[end];
            int ans = dp[size - 1];
            int max_next = 0;
            for(int i = end - 1; i >= begin; i--){
                dp[i - begin] = nums[i] + max_next;
                ans = max(ans, dp[i - begin]);
                max_next = max(dp[i - begin +1], max_next);
            }
            return ans;
        }
    
        int rob(vector<int>& nums) {
            int len = nums.size();
            if(len == 0)
                return 0;
            if(len == 1)
                return nums[0];
            return max(rob1(nums, 0, len - 2), rob1(nums, 1, len - 1));
        }
    };

[https_leetcode.com_problems_house-robber-ii]: https://leetcode.com/problems/house-robber-ii/
[http_blog.csdn.net_u010902721_article_details_46583815]: http://blog.csdn.net/u010902721/article/details/46583815