1.前言
力扣上有几道与打家劫舍相关的题目,算是学习动态规划时常被提及的经典试题,很有代表性,常在因内大大小小的社区内看到众人对此类问题的讨论。
学习最好的方式便是归纳总结、借鉴消化,基于这个目的,本文对此类问题也做了讲解,在一些优秀思想的基础上添加了个人观点。
闲话少说,进入正文,开始打家劫舍
,看今晚收获几何?
2. 线性盗贼
2.1 问题描述
一个专业的盗贼,计划偷打劫街的房屋。每间房内都藏有一定的现金,你可以进入每一间房子,影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被盗贼闯入,系统会自动报警。
现给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例1:
输入:[1,2,3,1]
输出:4
解释:偷窃 1
号房屋(金额=1),然后偷窃3
号房屋(金额=3
)。偷窃到的最高金额=1+3=4
。
示例2:
输入:[2,7,9,3,1]
输出:12
解释:偷窃 1
号房屋(金额 = 2),偷 3 号房屋(金 = 9),接着偷 5 号房屋(金额 =1)偷窃到的最高金额=2+9+1=12。
2.2 问题分析
在打劫之前先不要急入进入房间,应该是先做全局的估算。
想象当盗贼从第一间房屋开始偷窃,他可以选择是偷还是不偷。偷还是不偷的选择不是源于他瞬时良心上的发现,而是收益的多少。如果只有一间房间,他会毫不犹豫的选择偷,这样才能带来今晚最大的收益。
下图所示为当只有一间房子时盗贼能获取到的最高金额。
如果有 2
间房屋,盗贼面对第一间房屋时会如何想呢?
收益固然重要,但是如果触发了报警系统,偷鸡不成蚀把米这样的赔本生意,肯定是不能做的。所以他的想法是可以偷,如果从此房间内的获取到的收益大于从另一个房间内获取到受益,否则,放弃当前房间,而选择进入第二间房间。
文章来源:https://www.toymoban.com/news/detail-638070.html
怎么知道偷还是不偷哪一个获取的收益最大。唯一法则就是比较,也就偷和不偷两者的受益取其大。如果只文章来源地址https://www.toymoban.com/news/detail-638070.html
到了这里,关于C++动态规划经典试题解析之打家劫舍系列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!