专栏首页算法channel动态规划|相邻约束下的最优解

动态规划|相邻约束下的最优解

本篇进一步介绍动态规划的基本应用。

1

题目

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.

相邻房子不能同时偷,求在此约束下,偷n个房子获益的最大值。

2

分析

分析以下例子:

房子编号:0 1 2 3 4 5

房子收益:4 2 8 6 1 3

目标:偷n个房子获益的最大值。

约束条件:相邻房子不能同时偷。

可能的操作序列:

0 2 4

0 2 5

0 3 5

1 3 5

1 4

小偷面对编号为 i 的房子时,他会有两种决策:

1) 偷(暗含着前一个房子没偷)

2)不偷(注意不一定暗含着前一个房子一定偷了,如果想成前一个房子一定要偷,这就表示偷房子的序列为间隔性的能偷的最大钱数,这是不一定的,比如:3,2,2,3,最大收益为6,中间隔了两个房子!)

如何做决策?

分别比较下这两种决策下的最大能偷的钱数:

1)偷 i,能获得收益为: maxval = num[i] + premax,其中 premax 表示前一个房子没偷能拿到的最大钱数;

2)不偷 i,能获得最大收益为:premax 和前一个房子偷了能获得最大收益,的最大值,即 premax = max(premax, maxval),需要注意:

前一个房子偷了能获得最大收益 为上一步的maxval(它就是表示偷了 i,所以需要用一个临时变量存储起来,供下一个时步用)

可以看到这两种情况相互耦合

1)的premax实际上是上一时步 2)的premax

2)的maxval实际上是上一时步 1)的maxval

最后一步,遍历结束后,取 maxval和premax的最大值

3

代码

python代码,代码很简单,就几行,但是里面暗含的意义都非常大。

premax, maxval = 0,0 for val in nums: tmp = maxval maxval = val + premax premax = max(premax,tmp) return max(premax,maxval)

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划|相邻约束下的最优解(House Robber II )

    01 House Robber II This time, all houses at this place are arranged in a circl...

    double
  • 星火虽小,但我愿竭尽所能,为你带些温暖

    精选了近期推送的文章,读者朋友们不放抽一些时间学习下。要想比别人多掌握一些知识和技巧,只需要抽取一些零碎时间,反复过几遍。一方面学知识点,另一方面学他人的技巧也...

    double
  • 均分纸牌(经典贪心)

    有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。

    double
  • 高防服务器如何防御网络攻击?

    如今很多互联网公司都会选择高防服务代替普通服务器,因为高防服务器在配置、网络资源等方面都明显好于普通服务器,更重要的是,其防御网络攻击能力强于普通服务器。

    墨者安全科技
  • 解决pycharm安装第三方库失败的问题

    在使用pycharm学习python的时候,经常需要第三方库,没有第三方库程序就会报错,pycharm也会提醒你要安装所需要的库,安装第三方库的时候往往就出现了...

    砸漏
  • 高防服务器如何防御网络攻击?

    如今很多互联网公司都会选择高防服务代替普通服务器,因为高防服务器在配置、网络资源等方面都明显好于普通服务器,更重要的是,其防御网络攻击能力强于普通服务器。

    用户6764630
  • GDI编程

    由于最近一直在搞GDI(GDI+)和图片处理的东西,怕自己忘记(其实已经忘得差不多),就仿照网上的BITMAPINFO查看器,写了个东西。 工程下载地址:点击打...

    _gongluck
  • Android学期项目指导

    用户1733354
  • 大数据处理的一些总结和应用(有关舆情监控)

        说到大数据处理可能大家都不会陌生,这是近年来非常火热的话题,各行各业都想借助大数据为自己助力,有了这个工具,就好像在飞机上看农田一般清晰,一目了然,也也...

    流川疯
  • 带记忆电阻器的模拟内容可寻址存储器

    原文题目:Analog content addressable memories with memristors

    Jarvis Cocker

扫码关注云+社区

领取腾讯云代金券