LeetCode Q213: 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 arearranged 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.

Solution:

DP, when houses form a circle, we have to deal with two situation which cut a circle to array. Then solve two situation using solution of House Robber.

	class Solution {
	public:
	int profit(vector<int>& nums, vector<int>& t, int n){
	if(n<=0){
	t[n]=n==0? 0:t[n];
	return 0;
	}
	int p0=t[n]==-1? profit(nums, t, n-1):t[n];
	int p1=t[n]==-1? profit(nums, t, n-2)+nums[n-1]:t[n];
	t[n]=max(p0, p1);
	return t[n];
	}
	int rob(vector<int>& nums) {
	if(nums.size()==0)
	return 0;
	if(nums.size()==2)
	return max(nums[0], nums[1]);
	if(nums.size()==1)
	return nums[0];
	vector<int> nums0=nums;
	vector<int> nums1=nums;
	nums0.erase(nums0.begin());
	nums1.erase(nums1.begin(), nums1.begin()+2);
	nums1.erase(nums1.begin()+nums1.size()-1);
	vector<int> t0(nums0.size()+1, -1);
	vector<int> t1(nums1.size()+1, -1);
	int res0=profit(nums0, t0, nums0.size());
	int res1=nums[0]+profit(nums1, t1, nums1.size());
	return max(res0, res1);
	}
	};

view raw Q213HouseRobberII.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int helper(vector<int>& nums, int start, int end){
	if(start>end)
	return 0;
	vector<int> myT(end-start+2, 0);
	myT[1]=nums[start];
	for(int i = 2; i<=end-start+1; i++)
	myT[i] = max(myT[i-2]+nums[i+start-1], myT[i-1]);
	return myT.back();
	}
	int rob(vector<int>& nums) {
	if(nums.empty())
	return 0;
	int v0 = helper(nums, 0, nums.size()-2);
	int v1 = helper(nums, 1, nums.size()-3)+nums.back();
	return max(v0, v1);
	}
	};

view raw Q213Rnd2.cpp hosted with ❤ by GitHub