好的，我们这次来详细讲解 LeetCode 第 198 题「打家劫舍」。

1. 题目描述

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

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

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

示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃第 1 间房屋 (金额 = 2), 第 3 间 (金额 = 9)，第 5 间 (金额 = 1)。总金额 = 2 + 9 + 1 = 12。

2. 题意理解

• 不能偷相邻的两个房子。
• 要使得偷的总金额最大。
• 数组长度可能为 0（没有房子），也可能很长。
• 金额是非负整数。

3. 思路分析

3.1 暴力思路（不可行）

我们可以想到，对于每个房子，有两种选择：偷或不偷。但若偷了第 i 间，就不能偷第 i+1 间。
这种选择结构可以用递归枚举所有可能性，但时间复杂度是 O(2^n)，在 n 较大时超时。

3.2 动态规划思路

这是一个典型的 序列型动态规划 问题，可以用子问题递推求解。

定义状态：
dp[i] 表示偷到第 i 间房屋时（不一定偷第 i 间）能获得的最大金额。
但这样定义不够精确，更好的定义是：

dp[i] 表示考虑前 i 间房屋（从 0 到 i-1 号房屋）时能偷到的最大金额。

那么对于第 i 间房屋（即 nums[i-1]，如果下标从 1 开始数房屋编号）：

• 如果偷第 i 间房屋：则不能偷第 i-1 间，所以最大金额 = dp[i-2] + nums[i-1]
• 如果不偷第 i 间房屋：则最大金额 = dp[i-1]

取两者最大值：

\[dp[i] = \max(dp[i-1], \ dp[i-2] + nums[i-1]) \]

初始条件：

• dp[0] = 0（没有房屋可偷，金额为 0）
• dp[1] = nums[0]（只有一间房屋，只能偷它）

4. 逐步推导示例

示例 1：nums = [1,2,3,1]

• dp[0] = 0
• dp[1] = max(dp[0], nums[0]) = max(0, 1) = 1（其实直接是 nums[0]）
• dp[2] = max(dp[1], dp[0] + nums[1]) = max(1, 0+2) = max(1, 2) = 2
• dp[3] = max(dp[2], dp[1] + nums[2]) = max(2, 1+3) = max(2, 4) = 4
• dp[4] = max(dp[3], dp[2] + nums[3]) = max(4, 2+1) = max(4, 3) = 4

最终结果：dp[4] = 4

示例 2：nums = [2,7,9,3,1]

• dp[0] = 0
• dp[1] = 2
• dp[2] = max(2, 0+7) = 7
• dp[3] = max(7, 2+9) = 11
• dp[4] = max(11, 7+3) = 11
• dp[5] = max(11, 11+1) = 12

结果：12

5. 代码实现（带注释）

def rob(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    # dp[i] 表示前 i 个房屋能偷到的最大金额
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = nums[0]
    
    for i in range(2, n + 1):
        # 不偷第 i 间: dp[i-1]
        # 偷第 i 间: dp[i-2] + nums[i-1]
        dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
    
    return dp[n]

6. 空间优化

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

def rob(nums):
    prev = 0  # dp[i-2]
    curr = 0  # dp[i-1]
    for num in nums:
        # 计算 dp[i] = max(dp[i-1], dp[i-2] + num)
        prev, curr = curr, max(curr, prev + num)
    return curr

这样代码更简洁，且效率更高。

7. 总结

• 核心思路：动态规划，状态转移为是否偷当前房屋。
• 状态定义：dp[i] 表示前 i 间房屋的最大金额。
• 转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
• 初始条件：dp[0]=0, dp[1]=nums[0]
• 可优化空间到 O(1)。

这个题是动态规划的入门经典题，理解它对掌握序列型 DP 很有帮助。