#33. Money robbing

admin管理员组

文章数量:1558087

Problem description:

A robber is 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.

Sample input:

1 2 3 1

Sample output:

4

Sample explanation:

Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

1. 问题分析
原问题等价为在给定序列中找最大权重和，要求相邻两数不可同选
则可转化为在[1,n]区间上序列求最大 dp[x]
递推表达式如下： dp[x]= max(dp[x-1],dp[x-2] + nums[x])

2. 时间复杂度分析
只遍历一次数组，因此 T(n)=O(n);
 

#include<iostream>
#include<cmath>
using namespace std;

int money[1000000];
int rob[1000000];
int  cmax(int a,int b)
{
	return (a > b ? a : b);
}
int main()
{
	int i = 0,length=0;
	while (cin >> money[i])
	{
		i++;
		if (cin.get() == '\n')
			break;
	}
	length = i;
	
	if (length == 1)
	{
		cout<< money[0];
		
	}
	else
	{
		rob[0] = money[0];
		rob[1] = cmax(money[0], money[1]);

		for (i = 2; i <= length; i++)
		{
			//对第i个房子，如果抢-则为rob[i-2] + money[i]   ； 不抢则为rob[i - 1]
			rob[i] = cmax(rob[i - 1], (rob[i-2] + money[i]));

		}
		
		cout << rob[length];
	}	

}

本文标签： Moneyrobbing