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 andit 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:
Input:[2,3,2]Output:3Explanation:You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input:[1,2,3,1]Output:4Explanation:Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
一开始还想着要去记录当前答案有没有包含第一个元素，然后在最后最判断，这样好像会影响中间的结果，得到错误答案。看了讨论区，有一个很简洁的方法，因为头和尾是“互斥”的，所以分别去掉头和尾按照House Robber I来计算，取最大值就行了
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int start, int end) {
int pre1 = 0, pre2 = 0;
for (int i = start; i <= end; i++) {
int num = nums[i];
int cur = Math.max(pre1 + num, pre2);
pre1 = pre2;
pre2 = cur;
}
return pre2;
}
}
网友评论