跳至主要內容

 

labuladong约 978 字大约 3 分钟动态规划

Info

数据结构精品课open in new window递归算法专题课open in new window 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》open in new window 出版,签名版限时半价!

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
198. House Robberopen in new window198. 打家劫舍open in new window🟠
213. House Robber IIopen in new window213. 打家劫舍 IIopen in new window🟠
337. House Robber IIIopen in new window337. 打家劫舍 IIIopen in new window🟠
-剑指 Offer II 089. 房屋偷盗open in new window🟠
-剑指 Offer II 090. 环形房屋偷盗open in new window🟠

有读者私下问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,我发现这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。

打家劫舍系列总共有三道,难度设计非常合理,层层递进。第一道是比较标准的动态规划问题,而第二道融入了环形数组的条件,第三道更绝,把动态规划的自底向上和自顶向下解法和二叉树结合起来,我认为很有启发性。如果没做过的朋友,建议学习一下。

下面,我们从第一道开始分析。

打家劫舍 I

力扣第 198 题「打家劫舍open in new window」的题目如下:

街上有一排房屋,用一个包含非负整数的数组 nums 表示,每个元素 nums[i] 代表第 i 间房子中的现金数额。现在你是一名专业小偷,你希望尽可能多的盗窃这些房子中的现金,但是,相邻的房子不能被同时盗窃,否则会触发报警器,你就凉凉了。

请你写一个算法,计算在不触动报警器的前提下,最多能够盗窃多少现金呢?函数签名如下:

int rob(int[] nums);

比如说输入 nums=[2,1,7,9,3,1],算法返回 12,小偷可以盗窃 nums[0], nums[3], nums[5] 三个房屋,得到的现金之和为 2 + 9 + 1 = 12,是最优的选择。

题目很容易理解,而且动态规划的特征很明显。我们前文 动态规划详解 做过总结,解决动态规划问题就是找「状态」和「选择」,仅此而已

本文剩余内容为会员内容,请先购买 网站会员 open in new window ,然后 借助 Chrome 插件解锁网页 open in new window 或者 点这里open in new window 跳转小鹅通查看。

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释