🪴 Stone's Knowledge Garden

Search

SearchSearch

抢房子

Sep 26, 2024, 8 min read

团灭 LeetCode 打家劫舍问题

GitHub

通知：数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！另外，建议你在我的 网站 学习文章，体验更好。

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

LeetCode力扣难度
198. House Robber198. 打家劫舍🟠
213. House Robber II213. 打家劫舍 II🟠
337. House Robber III337. 打家劫舍 III🟠
-剑指 Offer II 089. 房屋偷盗🟠
-剑指 Offer II 090. 环形房屋偷盗🟠

-----------

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

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

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

打家劫舍 I

力扣第 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，是最优的选择。

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

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode力扣
-剑指 Offer II 089. 房屋偷盗
-剑指 Offer II 090. 环形房屋偷盗

＿＿＿＿＿＿＿＿＿＿＿＿＿

本文为会员内容，请扫码关注公众号或 点这里 查看：

====其他语言代码====

198.打家劫舍

213.打家劫舍II

337.打家劫舍III

python

Shantom 提供 198. House Robber I Python3 解法代码：

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 提供 213. House Robber II Python3 解法代码：

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 提供 337. House Robber III Python3 解法代码：

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

自顶向下

/**
 * @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)
};

自底向上

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]
};

自底向上 + 状态压缩

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

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

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]
}

Graph View

Backlinks