区块链技术博客
www.b2bchain.cn

#33. Money robbing

这篇文章主要介绍了#33. Money robbing,通过具体代码讲解7735并且分析了#33. Money robbing的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了#33. Money robbing。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=7735。具体如下:

 

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

 

本文地址https://www.b2bchain.cn/?p=7735

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » #33. Money robbing
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们