抢房子.md

# 团灭 LeetCode 打家劫舍问题

<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.gitee.io/pictures/souyisou1.png)

**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.1，[手把手刷二叉树系列课程](https://aep.xet.tech/s/3YGcq3) 上线，[第 17 期刷题打卡挑战](https://aep.xet.tech/s/2jPp5X) 下周开始，报名从速！。另外，建议你在我的 [网站](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=动态规划详解进阶) 做过总结，**解决动态规划问题就是找「状态」和「选择」，仅此而已**。




<hr>
<details>
<summary><strong>引用本文的题目</strong></summary>

<strong>安装 [我的 Chrome 刷题插件](https://mp.weixin.qq.com/s/X-fE9sR4BLi6T9pn7xP4pg) 点开下列题目可直接查看解题思路：</strong>

| LeetCode | 力扣 |
| :----: | :----: |
| - | [剑指 Offer II 089. 房屋偷盗](https://leetcode.cn/problems/Gu0c2T/?show=1) |
| - | [剑指 Offer II 090. 环形房屋偷盗](https://leetcode.cn/problems/PzWKhm/?show=1) |

</details>



**＿＿＿＿＿＿＿＿＿＿＿＿＿**

应合作方要求，本文不便在此发布，请扫码关注回复关键词「抢房子」或 [点这里](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_62987952e4b09dda12708bf8/1) 查看：

![](https://labuladong.gitee.io/pictures/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]
}
```