Chinaunix首页 | 论坛 | 博客
  • 博客访问: 20435
  • 博文数量: 2
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 30
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-19 10:51
文章分类

全部博文(2)

文章存档

2016年(2)

我的朋友

分类: C/C++

2016-07-04 15:31:16

原题:

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.

题意为给定一个数组,从数组中取出元素相加(不能连续取两个相邻的元素)能够得到的最大值

设P[k]为k个元素的数组能得出的最大值;
设M[k]为数组中索引为k - 1的元素值(索引值从0开始计数);

则有以下DP方程:
P[0] = 0;
P[1]=M(1);
P[k]=max(M(k) + P(k - 2), P(k-1)); (由于不能取相邻的元素,M(k) + P(k-2)表示取第k - 1个元素的值,P(k-1)表示不取第k - 1个元素的值)

则函数为:

点击(此处)折叠或打开

  1. int rob(int* nums, int numsSize) {
  2.     if (numsSize <= 0) return 0;
  3.     
  4.     if (numsSize == 1) return nums[0];
  5.   
  6.     int i, pm, ppm;
  7.     ppm = 0;
  8.     pm = nums[0];
  9.     for (i = 2; i <= numsSize; i++) {
  10.         int c1 = nums[i - 1] + ppm;
  11.         int c2 = pm;
  12.         
  13.         ppm = pm;
  14.         pm = (c1 > c2 ? c1 : c2);
  15.     }
  16.     
  17.     return pm;
  18. }

阅读(1246) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:重新设置linux中tcp默认的20秒connect超时时间

给主人留下些什么吧!~~