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;
                	}