LeetCode 213. House Robber II

, , , ,

Question

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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.

Example

1
2
3
4
5
6
7
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
             
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Solution

这道题是House Robber的follow up，但思路都是一样的。在某一点选择抢还是不抢当前物品，如果是抢当前物品，则是上一次的剩余 加上当前物品的价值；如果不抢当前这个的话，则会看前面的抢与不抢的最大值。对于这个题，该数组形成了一个一个circle，所以我们只需要比较两部分，其中是[0, n - 1] 和 [1, n]。这样保证第一个和最后一个元素不会碰撞。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// time:O(n) space:O(n)
   public int rob(int[] nums) {
       if (nums == null || nums.length == 0) return 0;
       int n = nums.length;
       if (n == 1) return nums[0];
       // 因为开头和结尾两个不能同时出现。
       int include = helper(nums, 0, n - 1); 
       int notInclude = helper(nums, 1, n);
       return Math.max(include, notInclude);
   }

   public int helper(int[] nums, int left, int right) {
       int rob = 0;
       int notRob = 0;
       for (int i = left; i < right; i++) {
           int temp = Math.max(rob, notRob);
           rob = notRob + nums[i];
           notRob = temp;
       }
       return Math.max(rob, notRob);
   }