198. 打家劫舍

题目

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

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

示例 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 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

解答

思路：DFS 回溯

首先按照回溯题来思考：原问题和子问题分别是什么？以及如何从原问题转移到子问题？这种时候从 第一个房子/最后一个房子 开始思考是最容易的，因为它们受到的约束最小。考虑的是：选或不选。以最后一个房子选或不选开始思考：

• 不选第 $n$ 个房子，那么问题变成前面 $n-1$ 个房子的问题
• 选第 $n$ 个房子，那么问题变成前面 $n-2$ 个房子的问题，只不过计算结果需要加上当前房子

回溯三问：

• 当前操作：枚举第 $i$ 个房子选还是不选
• 当前问题：从 前 $i$ 个房子 中可以得到的最大金额和
• 它的子问题：
  • 不选：从前 $i-1$ 个房子中可以得到的最大金额和，计算结果直接返回给当前问题
  • 选：从前 $i-2$ 个房子中可以得到的最大金额和，计算结果加上 nums[i] 返回给当前问题

注意：DP 和 DFS 只能表示从 一些 元素中计算出的结果，比如前 $n$ 个数之类的。这里把递归得到的金额作为返回值，把 $i$ 作为参数传入，递归方程为：

$$\text{dfs}(i)=max(\text{dfs}(i-1),\text{dfs}(i-2)+nums[i])$$

代码

Python 代码

# TLE
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        def dfs(i):
            if i < 0:
                return 0
            
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return res

        return dfs(n - 1)

由于回溯的时间复杂度是指数级别的，而枚举每个数选或不选有两种情况，因此时间复杂度为 $O(2^n)$，会超时。

思路：记忆化搜索

回头来看这棵搜索树：

可以看出计算了两次 dfs(2)。那么我们可以在第一次计算的时候把结果存储到 cache 数组或者哈希表中，这样第二次算的时候直接返回计算结果即可。优化后的搜索树：

优化后的搜索树每个节点至多遍历 2 次（第一次遍历和第二次访问），因此时间复杂度为 $O(2n)$。

DP 问题的复杂度分析：状态个数乘以单个状态的计算时间。而记忆化搜索由于需要存储递归函数的计算结果，因此空间复杂度也和状态个数有关。

• 时间复杂度为 $O(2n)$
• 空间复杂度为 $O(n)$

代码

Python 代码

Python 可以直接用 @cache 装饰器来做，它的原理是用一个哈希表来存储递归函数的中间结果（记录入参和对应的返回值）。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        @cache
        def dfs(i):
            if i < 0:
                return 0
            
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return res

        return dfs(n - 1)

也可以自己写一个 cache 数组来实现：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        cache = [-1] * n
        
        def dfs(i):
            if i < 0:
                return 0

            if cache[i] != -1:
                return cache[i]
            
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            cache[i] = res

            return res

        return dfs(n - 1)

思路：递推与空间优化

我们仔细分析递归树，可以发现：计算的过程只发生在子问题返回上一级问题 这一过程中。也就是说，我们可以从下往上计算：通过 dfs(0), dfs(1) 计算得到 dfs(2)，通过 dfs(1), dfs(2) 计算得到 dfs(3)，以此类推。

• 自顶向下算：记忆化搜索
• 自底往上算：递推

如何把记忆化搜索翻译成递推公式？

• dfs 变成 f 数组，f[i] 表示前 $i$ 个房子可以打劫到的最大金额
• 递归变成循环
• 递归边界变成数组初始值 f[0], f[1]

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

可以把负数下标改成：

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

注意这里是 f[i] 下标整体 + 2，也就是说现在的 f[n + 1] 等于原来的 f[n - 1]，就是答案。

代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * (n + 2)

        for i, x in enumerate(nums):
            f[i + 2] = max(f[i + 1], f[i] + x)
        
        return f[n + 1]

再做空间优化，从 $O(n)$ 到 $O(1)$：我们在计算 f[i] 时只需要它的上一个状态和上上一个状态。因此我们用 f0, f1 分别表示上上一个和上一个，就有：

$$f=max(f_1,f_0+nums[i]),\Rightarrow f_0=f_1,f_1=f$$

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        f0 = 0
        f1 = 0

        for x in nums:
            new_f = max(f1, f0 + x)
            f0 = f1
            f1 = new_f
        
        return f1 # 最后一次算出的 new_f