leetcode-198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, but adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the police will be automatically alerted.

Given a list of non-negative integers representing the amount of money in each house, determine the maximum amount you can rob tonight without alerting the police.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases, and to @ts for adding additional test cases.

Subscribe to see which companies asked this question.

暴力递归解法

先用暴力递归来求解：

int search(const vector<int>& nums, int index) {
		if (index >= nums.size())return 0;


		return  max(nums[index] + search(nums, index - 2),//偷这家
			search(nums, index - 1));//不偷这家
		return 0;
	}
	int rob(const vector<int>& nums) {

		return search(nums, nums.size()-1);//2^n

		return 0;
	}

动态规划解法

暴力递归会超时，原因是大量相同的子问题被重复计算——例如递归到 index=3 时，必然包含了 index=2 的计算。

可以用一个数组缓存每个位置的搜索结果，从而将暴力递归转换为 DP。自底向上按递推式推导下一个状态：状态 0 为 0，状态 1 只能偷取第一家。

	int rob(const vector<int>& nums) {
		int *arr=new int[nums.size()+10];

		memset(arr, 0, (sizeof (int))*(nums.size()+10));

		arr[0] = 0;
		arr[1] = nums[0];
		for (int  i = 2; i <= nums.size(); i++)
		{

			arr[i] = max(nums[i-1] + arr[i - 2], arr[i - 1]);

		}

		return arr[nums.size()];
		return 0;
	}