LeetCode:House Robber II淺析

LeetCode:House Robber II淺析

 

House Robber II

  Total Accepted:23515Total Submissions:78696Difficulty:Medium  

 

Note:This is an extension ofHouse 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 arearranged 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 tonightwithout alerting the police.

Credits:
Special thanks [email protected] adding this problem and creating all test cases.

 

Subscribeto see which companies asked this question

Hide Tags Dynamic Programming Hide Similar Problems (E) House Robber(M) Paint House(E) Paint Fence            

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LeetCode:House Robber的變形

 

code:

 

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        return max(_rob(nums,0,n-2),_rob(nums,1,n-1));
    }
    
    int _rob(vector& nums, int lo, int hi) {
        
        int preN = 0;
        int preY = 0;
        
        for(int i=lo;i<=hi;i++){
            int tmp = preY;
            preY = max(preN,preY);
            preN = tmp + nums[i];
        }
        return max(preN,preY);
    }
};