leecode 解题总结：198. House Robber

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:You are a PRofessional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.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.分析:一个盗贼，不能连续偷两个相邻的家，问今天最多能获取的财富是多少。举例:1 2 10 7 4 5 1,一种方式是如果遇到两家，尽量选择钱多的，问题就变成贪心但是如果1,2选择2，导致只能选择7，丢失了10，,10有可能是最大的。也就是说前面的选择会影响候选的选择状态。应该是一个dp问题,设dp[i]表示前面i户人家总共可以获得的最大利润dp[i]=max{dp[i-1] , dp[i-2] + A[i]}，当前的最大值一定来源于前面一个或者再前面一个的值边界:dp[0]=A[0],dp[1]=A[1]最大值是dp[n-1],n为数组长度1 2 8 7 4 5 1dp[0]=1,dp[1]=2,dp[2]=max{dp[1] , dp[0] + A[2]}=max{2,9}=9,dp[3]=max{dp[2], dp[1] + A[3]}=max{9 , 9}=9dp[4]=max{dp[3],dp[2]+A[4]}=max{9,9+4}=13dp[5]=max{dp[4],dp[3] + A[5]}=max{13,9+5}=14dp[6]=max{dp[5] ,dp[4]+A[6]}=max{14 , 13 + 1} = 14输入:7(元素个数)1 2 8 7 4 5 12 1 21142 1 1 2输出:14214关键:1 报错:Input:[2,1,1,2] ,Output:3,Expected:4原来可能跳过若干个值来做。这样dp方程就失效了。dp[i]=max{dp[i-1] , dp[j] + A[i]},其中j属于0到i-2而不是dp[i-2] + A[i]，当前dp值可能来源于前面任意一个dp值*/class Solution {public:    int rob(vector<int>& nums) {        if(nums.empty())		{			return 0;		}		int size = nums.size();		if(1 == size)		{			return nums.at(0);		}		if(2 == size)		{			return max(nums.at(0) , nums.at(1));		}		vector<int> dp(size , 0);		dp.at(0) = nums.at(0);		dp.at(1) = nums.at(1);		int result = INT_MIN;		int curResult = 0;		for(int i = 2 ; i < size ; i++)		{			curResult = dp.at(i-1);			for(int j = 0 ; j <= i - 2; j++)			{				curResult = max(curResult , dp.at(j) + nums.at(i));			}			dp.at(i) = curResult;			result = max(result , curResult);		}		return result;    }};void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 int answer = solution.rob(nums);		 cout << answer << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}