[LeetCode]House Robber

用localMax[i]表示前i + 1个house能够偷到的最大值。那么我们有递归公式：

• localMax[i] = max(localMax[i - 1], localMax[i - 2] + house[i])

也就是说对于house[i]来说，只有两种情况，偷或者不偷，我们取其中最大的一种情况。时间复杂度O(n)，可以优化到常数空间，代码如下：

	class Solution {
	public:
	int rob(vector<int>& nums) {
	int len = nums.size(), localMax1 = 0, localMax2 = 0;
	for(int i = 0; i < len; ++i)
	{
	int currMax = max(localMax1 + nums[i], localMax2);
	localMax1 = localMax2;
	localMax2 = currMax;
	}
	return max(localMax1, localMax2);
	}
	};

view raw House Robber.cpp hosted with ❤ by GitHub