House Robber II

题目来源
Design a data structure that supports the following two operations:
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.
和上一道题的区别就是一个是线段,一个是环,上一个直接用dp就可以了,这个应该怎么用呢?没啥想法,看答案吧。因为我现在要快速刷题…所以想不出来就看答案。
可以通过假定i是否被抢劫来断开环。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return n ? nums[0] : 0;
        return max(robber(nums, 0, n-2), robber(nums, 1, n-1));
    }
    
    int robber(vector<int> &nums, int l, int r)
    {
        int pre = 0, cur = 0;
        for (int i=l; i<=r; i++) {
            int tmp = cur;
            cur = max(cur, pre + nums[i]);
            pre = tmp;
        }
        return cur;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,959评论 0 23
  • 生命中总有一个你不敢想不敢去多想的人,或过因过分憎恨或已失去的深爱。
    一盒糖大西瓜阅读 198评论 0 0
  • 放假对于多数人而言,不得不说是件欢快的事情。除了不管别人的事以外,几乎都觉得可以少看到一些人的嘴脸,如此,让自己更...
    情定高三季阅读 205评论 0 0
  • 父亲,这两个字的份量在我心里,一直很沉重。今天是父亲节,我思绪万千。如今父亲已经立暮之年,我也已为人妻为人母。 关...
    倔强的鱼阅读 274评论 0 0
  • 六一儿童节的今天,向各位大朋友、小朋友们说一声“儿童节快乐”,这一期的文章有点特别,与儿童节有关,如果有空带着轻松...
    苏宇城阅读 1,186评论 1 13