算法 动态规划 打家劫舍

分析得出，dp[k] = max(dp[k-1],dp[k-2]+nums[k])

int rob(vector& nums)
{
	int n = nums.size();
	if (n <= 0) return 0;
	if (n == 1) return nums[1];
	vector dp(n, 0);
	dp[1] = nums[1];
	dp[2] = max(nums[1], nums[2]);
	for (int i = 3; i < n; ++i)
	{
		dp[i] = max[dp[i - 2], dp[i - 1] + nums[i]];
	}
	return dp[n - 1];
}

打家劫舍升级版