# 团灭 LeetCode 打家劫舍问题
![](https://labuladong.github.io/algo/images/souyisou1.png)
**通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0;点击这里体验 [刷题全家桶](https://labuladong.gitee.io/algo/images/others/%E5%85%A8%E5%AE%B6%E6%A1%B6.jpg)。另外,建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章,体验更好。**
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [198. House Robber](https://leetcode.com/problems/house-robber/) | [198. 打家劫舍](https://leetcode.cn/problems/house-robber/) | 🟠
| [213. House Robber II](https://leetcode.com/problems/house-robber-ii/) | [213. 打家劫舍 II](https://leetcode.cn/problems/house-robber-ii/) | 🟠
| [337. House Robber III](https://leetcode.com/problems/house-robber-iii/) | [337. 打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/) | 🟠
| - | [剑指 Offer II 089. 房屋偷盗](https://leetcode.cn/problems/Gu0c2T/) | 🟠
| - | [剑指 Offer II 090. 环形房屋偷盗](https://leetcode.cn/problems/PzWKhm/) | 🟠
**-----------**
有读者私下问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,我发现这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。
打家劫舍系列总共有三道,难度设计非常合理,层层递进。第一道是比较标准的动态规划问题,而第二道融入了环形数组的条件,第三道更绝,把动态规划的自底向上和自顶向下解法和二叉树结合起来,我认为很有启发性。如果没做过的朋友,建议学习一下。
下面,我们从第一道开始分析。
### 打家劫舍 I
力扣第 198 题「打家劫舍」的题目如下:
街上有一排房屋,用一个包含非负整数的数组 `nums` 表示,每个元素 `nums[i]` 代表第 `i` 间房子中的现金数额。现在你是一名专业小偷,你希望**尽可能多**的盗窃这些房子中的现金,但是,**相邻的房子不能被同时盗窃**,否则会触发报警器,你就凉凉了。
请你写一个算法,计算在不触动报警器的前提下,最多能够盗窃多少现金呢?函数签名如下:
```java
int rob(int[] nums);
```
比如说输入 `nums=[2,1,7,9,3,1]`,算法返回 12,小偷可以盗窃 `nums[0], nums[3], nums[5]` 三个房屋,得到的现金之和为 2 + 9 + 1 = 12,是最优的选择。
题目很容易理解,而且动态规划的特征很明显。我们前文 [动态规划详解](https://labuladong.github.io/article/fname.html?fname=动态规划详解进阶) 做过总结,**解决动态规划问题就是找「状态」和「选择」,仅此而已**。
引用本文的题目
安装 [我的 Chrome 刷题插件](https://mp.weixin.qq.com/s/X-fE9sR4BLi6T9pn7xP4pg) 点开下列题目可直接查看解题思路:
| LeetCode | 力扣 |
| :----: | :----: |
| - | [剑指 Offer II 089. 房屋偷盗](https://leetcode.cn/problems/Gu0c2T/?show=1) |
| - | [剑指 Offer II 090. 环形房屋偷盗](https://leetcode.cn/problems/PzWKhm/?show=1) |
**_____________**
应合作方要求,本文不便在此发布,请扫码关注回复关键词「抢房子」或 [点这里](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_62987952e4b09dda12708bf8/1) 查看:
![](https://labuladong.github.io/algo/images/qrcode.jpg)
======其他语言代码======
[198.打家劫舍](https://leetcode-cn.com/problems/house-robber)
[213.打家劫舍II](https://leetcode-cn.com/problems/house-robber-ii)
[337.打家劫舍III](https://leetcode-cn.com/problems/house-robber-iii)
### python
[Shantom](https://github.com/Shantom) 提供 198. House Robber I Python3 解法代码:
```Python
class Solution:
def rob(self, nums: List[int]) -> int:
# 当前,上一间,上上间
cur, pre1, pre2 = 0, 0, 0
for num in nums:
# 当前 = max(上上间+(抢当前),上间(放弃当前))
cur = max(pre2 + num, pre1)
pre2 = pre1
pre1 = cur
return cur
```
[Shantom](https://github.com/Shantom) 提供 213. House Robber II Python3 解法代码:
```Python
class Solution:
def rob(self, nums: List[int]) -> int:
# 只有一间时不成环
if len(nums) == 1:
return nums[0]
# 该函数同198题
def subRob(nums: List[int]) -> int:
# 当前,上一间,上上间
cur, pre1, pre2 = 0, 0, 0
for num in nums:
# 当前 = max(上上间+(抢当前),上间(放弃当前))
cur = max(pre2 + num, pre1)
pre2 = pre1
pre1 = cur
return cur
# 不考虑第一间或者不考虑最后一间
return max(subRob(nums[:-1]), subRob(nums[1:]))
```
[Shantom](https://github.com/Shantom) 提供 337. House Robber III Python3 解法代码:
```Python
class Solution:
def rob(self, root: TreeNode) -> int:
# 返回值0项为不抢该节点,1项为抢该节点
def dp(root):
if not root:
return 0, 0
left = dp(root.left)
right = dp(root.right)
# 抢当前,则两个下家不抢
do = root.val + left[0] + right[0]
# 不抢当前,则下家随意
do_not = max(left) + max(right)
return do_not, do
return max(dp(root))
```
### javascript
#### House Robber I
自顶向下
```js
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
let memo = new Array(nums.length);
memo.fill(-1, 0, nums.length)
// 返回nums[start..]能抢到的最大值
let dp = function (nums, start) {
if (start >= nums.length) {
return 0;
}
// 避免重复计算
if (memo[start] !== -1) return memo[start];
let res = Math.max(
// 不抢,去下一家
dp(nums, start + 1),
// 抢, 然后去下下家抢
nums[start] + dp(nums, start + 2)
)
// 记入备忘录
memo[start] = res;
return res;
}
// 强盗从第 0 间房子开始决定抢劫哪家
return dp(nums, 0)
};
```
自底向上
```js
var rob = function (nums) {
let n = nums.length;
// dp[i] = x 表示:
// 从第 i 间房子开始抢劫,最多能抢到的钱为 x
// base case: dp[n] = 0
let dp = new Array(n + 2);
dp.fill(0, 0, n + 2)
for (let i = n - 1; i >= 0; i--) {
dp[i] = Math.max(
dp[i + 1],
nums[i] + dp[i + 2]
)
}
// 强盗从第 0 间房子开始决定抢劫哪家
return dp[0]
};
```
自底向上 + 状态压缩
```js
var rob = function (nums) {
let n = nums.length;
// 记录 dp[i+1] 和 dp[i+2]
let dp_i_1 = 0, dp_i_2 = 0;
// 记录 dp[i]
let dp_i = 0;
for (let i = n - 1; i >= 0; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
};
```
#### House Robber II
```js
var rob = function (nums) {
let n = nums.length;
if (n === 1) return nums[0];
// 仅计算闭区间 [start,end] 的最优结果
let robRange = function (nums, start, end) {
let dp_i_1 = 0, dp_i_2 = 0;
let dp_i = 0;
for (let i = end; i >= start; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
return Math.max(
robRange(nums, 0, n - 2),
robRange(nums, 1, n - 1)
)
};
```
#### House Robber III
```js
var rob = function (root) {
let res = dp(root);
return Math.max(res[0], res[1]);
};
var dp = function (root){
if(root == null){
return [0,0];
}
let left = dp(root.left);
let right = dp(root.right);
// 抢,下家就不能抢了
let rob = root.val + left[0] + right[0];
// 不抢,下家可抢可不抢,取决于收益大小
let not_rob = Math.max(left[0], left[1]) + + Math.max(right[0], right[1]);
return [not_rob, rob]
}
```