由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁」
按照操作即可解锁本站全部文章
数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
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);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
int rob(vector<int>& nums);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
def rob(nums: List[int]) -> int:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
func rob(nums []int) int
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var rob = function(nums) {}
比如说输入 nums=[2,1,7,9,3,1]
,算法返回 12,小偷可以盗窃 nums[0], nums[3], nums[5]
三个房屋,得到的现金之和为 2 + 9 + 1 = 12,是最优的选择。
题目很容易理解,而且动态规划的特征很明显。我们前文 动态规划详解 做过总结,解决动态规划问题就是找「状态」和「选择」,仅此而已。
_____________
应合作方要求,本文不便在此发布,请扫码关注回复关键词「抢房子」或 点这里 查看:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释