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 1
dp[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}=9
dp[4]=max{dp[3],dp[2]+A[4]}=max{9,9+4}=13
dp[5]=max{dp[4],dp[3] + A[5]}=max{13,9+5}=14
dp[6]=max{dp[5] ,dp[4]+A[6]}=max{14 , 13 + 1} = 14

输入:
7(元素个数)
1 2 8 7 4 5 1
2 
1 2
1
1
4
2 1 1 2
输出:
14
2
1
4


关键:
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值
上述分析是错误的。
但是可以作为一种普遍的方法，对于dp[i]来源于任意dp[j]任意值方法适用
2 【下面需要看，重要】
dp[i]=max{dp[i-1] , dp[i-2] + A[i]}，当前的最大值一定来源于前面一个或者再前面一个的值
边界:dp[0]=A[0], dp[1]=max(A[0], A[1])，因为仅有两家选择其中大的， 而不是dp[1]=A[1]



*/

class Solution {
public:
    int rob2(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;
    }

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

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