LeetCode House Robber II

LeetCode House Robber II

Note: This is an extension of House 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 are arranged 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 tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.


本题是LeetCode House Robber的扩展版,当首尾相连时,怎样偷到最多的钱。

因为首尾相连,所以如果偷了第一家,就不能偷最后一家;或者如果偷了最后一家,就不能偷第一家。所以我们可以把数组分成两个部分,一部分是去掉最后一家,求一个最大值;另一部分是去掉第一家,求一个最大值。最优结果就是这两个最大值的最大值。

代码如下:

class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.size() == 0)return 0;
		if (nums.size() == 1)return nums[0];
		int ans1 = 0, ans2 = 0;
		vector<vector<int>> dp1(nums.size() + 1, vector<int>(2, 0)), dp2(nums.size() + 1, vector<int>(2, 0));
		for (int i = 1; i < nums.size(); ++i) { // 不偷最后一家
			dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][1]);
			dp1[i][1] = dp1[i - 1][0] + nums[i - 1];
			ans1 = max(ans1, max(dp1[i][0], dp1[i][1]));
		}
		for (int i = 2; i <= nums.size(); ++i) { // 不偷第一家
			dp2[i][0] = max(dp2[i - 1][0], dp2[i - 1][1]);
			dp2[i][1] = dp2[i - 1][0] + nums[i - 1];
			ans2 = max(ans2, max(dp2[i][0], dp2[i][1]));
		}
		return max(ans1, ans2);
	}
};

本代码提交AC,用时3MS。

更漂亮的代码是:

class Solution {
private:
	int subrob(const vector<int>& nums, int left, int right) {
		int robsum = 0, norobsum = 0;
		for (int i = left; i <= right; ++i) {
			int nrs = max(robsum, norobsum);
			int rs = norobsum + nums[i];
			norobsum = nrs;
			robsum = rs;
		}
		return max(robsum, norobsum);
	}
public:
	int rob(vector<int>& nums) {
		int n = nums.size();
		if (n == 0)return 0;
		if (n == 1)return nums[0];
		return max(subrob(nums, 0, n - 2), subrob(nums, 1, n - 1));
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *