算法学习

Appearance

198. 打家劫舍 Medium ​

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路 ​

输入： 一个代表每个房子的金额的数组 nums

输出： 在不能偷相邻房子的前提下，返回能偷的最大金额

本题属于线性DP问题。

1. 将问题抽象成动态规划问题 ​

这是一个“子问题最优解构成整体最优解”的问题，符合动态规划的特征：

  • 如果你偷了第 i 个房子，就不能偷第 i-1 个；
  • 如果你不偷第 i 个房子，可以继承 i-1 的最优解。

2. 状态定义 ​

令 f[i] 表示从前 i 个房子中能偷到的最大金额（下标从 0 开始）。

3. 状态转移方程 ​

对于每一个房子 i，有两种选择：

  • 不偷第 i 个房子：最大收益是 f[i-1]
  • 偷第 i 个房子：最大收益是 f[i-2] + nums[i]

所以：

python
f[i] = max(f[i - 1], f[i - 2] + nums[i])

4. 初始条件 ​

python
f[0] = nums[0]                   # 只有一个房子，只能偷它
f[1] = max(nums[0], nums[1])     # 两个房子，偷金额较大的那个

5. 目标值 ​

最终答案是 f[n - 1]，即偷完所有房子后能获得的最大金额。

代码实现 ​

滚动数组解法 ​

python
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 初始化两个状态：
        # f0 表示不偷当前房子的最大收益
        # f1 表示偷当前房子的最大收益（新计算）
        f0, f1 = 0, 0

        for num in nums:
            # 偷当前房子 = 上一个不偷 + 当前价值
            # 不偷当前房子 = 上一个偷 or 不偷中较大值（其实就是 f1）
            new_f = max(f0 + num, f1)
            f0 = f1
            f1 = new_f
        
        return f1
javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    let f0 = 0;
    let f1 = 0;

    for (let x of nums) {
        const newF = Math.max(f0 + x, f1);
        f0 = f1;
        f1 = newF;
    }

    return f1;
};

记忆化递归解法 ​

python
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 从前往后偷法
        n = len(nums)
        # 缓存已计算过的答案
        cache = [-1] * n
        def dfs(i):
            # 超过最后一家就没得抢了
            if i >= n:
                return 0
            # 当之前已经计算过则直接返回答案
            if cache[i] != -1:
                return cache[i]
            # 当偷了第 i 家就代表要在剩下的 i + 2 家里找到最大值
            # 当跳过第 i 家就代表要在剩下的 i + 1 家里找到最大值
            res = max(dfs(i + 1), dfs(i + 2) + nums[i])
            # 缓存当前计算结果
            cache[i] = res
            return res
        return dfs(0)

        # 从后往前偷法
        n = len(nums)
        cache = [-1] * n
        def dfs(i):
            # 当递归到 0 之前就返回 0 元
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
            # 当偷了第 i 家就代表要在剩下的 i - 2 家里找到最大值
            # 当跳过第 i 家就代表要在剩下的 i - 1 家里找到最大值
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            cache[i] = res
            return res
        # 从最后一家开始偷
        return dfs(n - 1)
javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // 从前往后偷法
    const cache = {};
    function dfs(i) {
        if (i >= nums.length) return 0;

        if (cache[i] != null) return cache[i];

        const res = Math.max(dfs(i + 1), dfs(i + 2) + nums[i]);

        cache[i] = res;

        return res;
    }

    return dfs(0); 
    
    // 从后往前偷法
    const cache = {};
    function dfs(i) {
        if (i < 0) return 0;

        if (cache[i] != null) return cache[i];

        const res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);

        cache[i] = res;

        return res;
    }

    return dfs(nums.length - 1);
};

复杂度分析 ​

时间复杂度：O(n)

空间复杂度：

  • 滚动数组解法：O(1）
  • 记忆化递归解法：O(n)

链接 ​

198 国际版

198 中文版