注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex213 House Robber II  

2015-05-20 23:04:38|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题是House Robber的升级版,拐了一个弯

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.


就是要求不能首尾同时选择,其实在思考这个题的时候直观能想到0-n-2动态遍历一次得到结果,然后2-n-1遍历一次,接着求最大值。不过没有经过理论分析的结果貌似都不靠谱。其实刚才说的两种遍历刚好是0-n-1遍历的一个子集,具体分析如下图
ex213 House Robber II - HT - HT·生活
 
代码如下所示

//动态规划的思想
/*维护一个数组dp,dp[i]表示到了i,非相邻元素的最大和
*这样的可以得到dp{i] = max(num[i]+dp[i-2],dp[i-1))
*/

int max(int a, int b)
{
return a > b ? a : b;
}
/*
* 关于原来的house robber,再归纳一遍
* 假设dp[i]是偷到i家时候的最大值
* dp[0] = nums[0] 因为只有一家
* dp[1] = max(nums[0],num[1])
* 当偷到第三家的时候,dp[2] = max(dp[1],dp[0]+nums[2]) 因为偷了第二家不可能再偷第三家
* 但是偷了第一家后可以偷第三家
*/
int traverse(int* nums, int numsSize)
{
int i = 0;
int *dp = (int*)malloc(numsSize*sizeof(int));
if (numsSize <= 0)
return 0;

dp[0] = nums[0];
dp[1] = max(nums[1], nums[0]);

int pre1, pre2;
for (i = 2; i < numsSize; i++)
{
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
}
int result = dp[numsSize - 1];
//free(dp);
//dp = NULL;
return result;
}
int rob(int* nums, int numsSize) {
if (numsSize <= 0)
return 0;
if (numsSize == 1)
return nums[0];
int result1, result2;
result1 = traverse(nums + 1, numsSize - 1);//从第二家到最后
result2 = traverse(nums, numsSize - 1); //从第一家到倒数第二家
return max(result1, result2);
}



  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017