## Monday, July 24, 2017

### [Leetcode] House Robber II, Solution

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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.

[Thoughts]

1. 抢劫house 0，那么就不能抢劫house n-1，所以抢劫的范围就是[0, n-2]
2. 不抢劫house 0，那么就得从house 1开始抢，抢劫的范围就是[1, n-1]

[Code]

``````1:    int rob(vector<int>& nums) {
2:      int len = nums.size();
3:
4:      if(len == 0) return 0;
5:      if(len == 1) return nums[0];
6:
7:      return max(robList(nums, 0, len -2), robList(nums, 1, len-1));
8:    }
9:
10:    int robList(vector<int>& nums, int start, int end) {
11:      int rob=0, no_rob=0;
12:      for(int i = start; i<= end; i++) {
13:        int new_rob = no_rob + nums[i];
14:        no_rob = max(rob, no_rob);
15:        rob = new_rob;
16:      }
17:
18:      return max(rob, no_rob);
19:    }
``````