LeetCode 213 - House Robber II

作者 QIFAN 日期 2017-01-03
LeetCode 213 - House Robber II

原题链接:213. House Robber II


题干

这是 198. House Robber 的延伸题。

唯一的不同点是这次是一个环状数组。
规则依旧是:不能在同一天晚上洗劫相邻的两个房子。

思路

假设有 n 幢房子,每幢房子所含的钱用数组 a 表示。
假设一个数组 memo 来记录最大可抢金额。
非环状时思路是 memo[i] = max(memo[i - 1], memo[i - 2] + a[i])

变成环状以后,其他地方都没有变,只是要考虑头和尾不能同时被抢劫。所以思路很简单,只要计算(0, a.length - 2) 和 (1, a.length - 1) ,保证头尾不被同时抢劫,比较最大值即可。

时间复杂度为 $O(n)$

代码:

public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
}
private int rob(int[] num, int lo, int hi) {
// include 就是抢这户,exclude 就是放过这户
int include = 0, exclude = 0;
for (int j = lo; j <= hi; j++) {
int i = include, e = exclude;
include = e + num[j];
exclude = Math.max(e, i);
}
return Math.max(include, exclude);
}