我来给你讲解 LeetCode 第 198 题「打家劫舍」。

题目描述

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

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

示例：

• 输入：[1,2,3,1]
• 输出：4
• 解释：偷窃第 1 间房（金额 = 1）和第 3 间房（金额 = 3），总金额 = 4。

解题思路

第一步：理解问题本质

这是一个典型的动态规划问题。我们需要在不能选择相邻元素的前提下，从数组中选择若干元素，使它们的和最大。

第二步：定义状态

定义 dp[i] 表示考虑前 i 个房屋时能偷窃到的最高金额。

这里有个关键点：dp[i] 不一定表示一定要偷第 i 个房屋，而是表示在前 i 个房屋这个范围内能获得的最大金额。

第三步：状态转移方程

对于第 i 个房屋（下标 i-1），我们有两种选择：

1. 偷第 i 个房屋：那么就不能偷第 i-1 个房屋，此时最大金额 = dp[i-2] + nums[i-1]
2. 不偷第 i 个房屋：那么最大金额 = dp[i-1]

因此状态转移方程为：
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

第四步：边界条件

• dp[0] = 0（没有房屋可偷）
• dp[1] = nums[0]（只有一间房屋，直接偷）

第五步：具体推导过程

以示例 [1,2,3,1] 为例：

• dp[0] = 0（没有房屋）
• dp[1] = max(dp[0], nums[0]) = max(0, 1) = 1
• dp[2] = max(dp[1], dp[0] + nums[1]) = max(1, 0 + 2) = 2
• dp[3] = max(dp[2], dp[1] + nums[2]) = max(2, 1 + 3) = 4
• dp[4] = max(dp[3], dp[2] + nums[3]) = max(4, 2 + 1) = 4

最终结果：dp[4] = 4

第六步：空间优化

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，我们可以用两个变量代替整个 dp 数组，将空间复杂度从 O(n) 降到 O(1)。

def rob(nums):
    if not nums:
        return 0
    
    # 用两个变量代替dp数组
    prev2 = 0  # 相当于dp[i-2]
    prev1 = 0  # 相当于dp[i-1]
    
    for num in nums:
        # 计算当前最大值
        current = max(prev1, prev2 + num)
        # 更新状态
        prev2 = prev1
        prev1 = current
    
    return prev1

第七步：算法分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只用了常数级别的额外空间

第八步：关键理解点

1. 状态定义：dp[i] 表示考虑前 i 个房屋时的最大金额，不是必须偷第 i 个房屋
2. 状态转移：每个位置都有偷和不偷两种选择，取最大值
3. 空间优化：由于状态转移只依赖前两个值，可以用滚动变量优化

这个问题的核心思想是在约束条件下做出最优选择，是理解动态规划的经典例题。