首页 > 其他 > 详细

House Robber II -- leetcode

时间:2015-08-16 16:45:08      阅读:279      评论:0      收藏: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.


基本思路:

将此问题分解为两个子问题。

设屋子总数为n。

1. 抢第1间屋。此时,最后一间屋不能抢了。则可抢范围是[0, n-1]

2. 不抢第1间屋。此时,最后一间屋可以抢。 则可抢范围是[1, n]


class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        return max(rob(nums, 0, nums.size()-1), rob(nums, 1, nums.size()));
    }
    
    int rob(vector<int>& nums, int start, int stop) {
        int last_last = 0, last = 0;
        for (int i=start; i<stop; i++) {
            int temp = max(last_last+nums[i], last);
            last_last = last;
            last = temp;
        }
        return last;
    }
};


版权声明:本文为博主原创文章,未经博主允许不得转载。

House Robber II -- leetcode

原文:http://blog.csdn.net/elton_xiao/article/details/47702551

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!