由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁」
按照操作即可解锁本站全部文章
通知: 数据结构精品课 V1.7 持续更新中;B 站可查看 核心算法框架系列视频。
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
牛客 | LeetCode | 力扣 | 难度 |
---|---|---|---|
- | 198. House Robber | 198. 打家劫舍 | 🟠 |
- | 213. House Robber II | 213. 打家劫舍 II | 🟠 |
- | 337. House Robber III | 337. 打家劫舍 III | 🟠 |
- | - | 剑指 Offer II 089. 房屋偷盗 | 🟠 |
- | - | 剑指 Offer II 090. 环形房屋偷盗 | 🟠 |
———–
有读者私下问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,我发现这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。
打家劫舍系列总共有三道,难度设计非常合理,层层递进。第一道是比较标准的动态规划问题,而第二道融入了环形数组的条件,第三道更绝,把动态规划的自底向上和自顶向下解法和二叉树结合起来,我认为很有启发性。如果没做过的朋友,建议学习一下。
下面,我们从第一道开始分析。
力扣第 198 题「 打家劫舍」的题目如下:
街上有一排房屋,用一个包含非负整数的数组 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,是最优的选择。
题目很容易理解,而且动态规划的特征很明显。我们前文 动态规划详解 做过总结,解决动态规划问题就是找「状态」和「选择」,仅此而已。
_____________
应合作方要求,本文不便在此发布,请扫码关注回复关键词「抢房子」或 点这里 查看:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释