打家劫舍 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

本题视频讲解

请看动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

答疑

问：为什么只需要考虑从左往右（从右往左）偷？我就不能从中间开始偷吗？

答：先偷 A 再偷 B，先偷 B 再偷 A，都是一样的，因为我们只关心最终能偷多少钱。推广，任意一种偷房子的顺序，都可以重新排列成从左到右（从右往左）偷。

一、递归搜索 + 保存计算结果 = 记忆化搜索

Python 解法1C++ 解法1

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dfs(i) 表示从 nums[0] 到 nums[i] 最多能偷多少
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            if i < 0:  # 递归边界（没有房子）
                return 0
            return max(dfs(i - 1), dfs(i - 2) + nums[i])

        return dfs(len(nums) - 1)  # 从最后一个房子开始思考

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n, -1); // -1 表示没有计算过

        // lambda 递归函数
        // dfs(i) 表示从 nums[0] 到 nums[i] 最多能偷多少
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i < 0) { // 递归边界（没有房子）
                return 0;
            }
            if (memo[i] != -1) { // 之前计算过
                return memo[i];
            }
            return memo[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]);
        };

        return dfs(n - 1); // 从最后一个房子开始思考
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (n)$ 。

二、1:1 翻译成递推

直接翻译的话， $dfs (i)$ 翻译成 $f [i]$ 。

但记忆化搜索会访问 $dfs (- 2)$ 和 $dfs (- 1)$ ， $f [- 2]$ 和 $f [- 1]$ 下标越界了。

解决办法：在 $f$ 数组的前面插入两个 $0$ ，把 $f$ 数组整体往右偏移 $2$ 位。偏移后， $dfs (i)$ 翻译成 $f [i + 2]$ 。

注意只有 $f$ 发生了偏移， $nums$ 并没有偏移。

Python 解法3C++ 解法3

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        f = [0] * (len(nums) + 2)
        for i, x in enumerate(nums):
            f[i + 2] = max(f[i + 1], f[i] + x)
        return f[-1]

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 2);
        for (int i = 0; i < n; i++) {
            f[i + 2] = max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }
};

复杂度分析

时间复杂度： $O (n)$ 。其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (n)$ 。

三、空间优化

Python 解法5C++ 解法5

python

class Solution:
    def rob(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

cpp

// C++ 版待补充

C++ 解法6

cpp

class Solution {
public:
    int rob(vector<int>& nums) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            int new_f = max(f1, f0 + x);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

复杂度分析

时间复杂度： $O (n)$ 。其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (1)$ 。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

本题视频讲解 ​

答疑 ​

一、递归搜索 + 保存计算结果 = 记忆化搜索 ​

复杂度分析 ​

二、1:1 翻译成递推 ​

复杂度分析 ​

三、空间优化 ​

复杂度分析 ​

分类题单 ​

本题视频讲解

答疑

一、递归搜索 + 保存计算结果 = 记忆化搜索

复杂度分析

二、1:1 翻译成递推

复杂度分析

三、空间优化

复杂度分析

分类题单