198. 打家劫舍

题目链接：198. 打家劫舍

题目描述

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

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

核心思考：动态规划（自顶向下 + 记忆化）

本题是典型的线性动态规划问题。对于每一间房屋 i，我们的决策只有两种：偷或者不偷。

1. 状态定义：设 dfs(i) 为从第 0 间到第 i 间房屋能够偷到的最高金额。
2. 状态转移逻辑：
   • 如果偷第 i 间房：那么我们不能偷第 i-1 间房，获取的总金额为 dfs(i-2) + nums[i]。
   • 如果不偷第 i 间房：那么我们能获取的最大金额就是前一间房为止的最大值 dfs(i-1)。
   • 综上推导出转移方程：dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i])。
3. 递归与记忆化：
   使用自顶向下的递归结合 Python 的 @cache 装饰器。这能够避免在递归过程中对同一索引位置的重复计算，将指数级的时间复杂度降为线性。
4. 终止条件：当 i < 0 时，说明已经没有房屋可以考虑，返回 0。

解题思路 (Python)

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def dfs(i):
            # 边界条件：没有房子可偷
            if i < 0:
                return 0
            
            # 状态转移：max(不偷当前家, 偷当前家且跳过前一家)
            return max(dfs(i - 1), dfs(i - 2) + nums[i])

        return dfs(len(nums) - 1)

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。得益于记忆化缓存，每个状态 dfs(i) 仅需被计算一次。
• 空间复杂度：$O(N)$。主要由递归堆栈深度以及缓存存储开销决定。