198. 打家劫舍 - House Robber

🎯 问题描述（来源于LeetCode）

描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums，请计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

说明：

  • 不能偷窃相邻的房屋。
  • 数组长度至少为 1。

示例：

  • 示例 1：
1
2
3
输入: nums = [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额=1) ，然后偷窃 3 号房屋 (金额=3)。总金额 = 1+3 = 4。
  • 示例 2：
1
2
3
输入: nums = [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (2), 3 号房屋 (9)，接着偷 5 号房屋 (1)。总金额 = 2+9+1 = 12。

💻 解题思路

思路：动态规划

算法步骤

  1. 定义 dp[i] 表示偷窃前 i 间房屋（房屋编号从 1 到 i，即 nums[0..i-1]）能获得的最大金额。
  2. 初始化 dp[0] = 0（没有房屋），dp[1] = nums[0]（只有第一间）。
  3. 对于 i 从 2 到 n，状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
    • 不偷第 i 间：金额为 dp[i-1]。
    • 偷第 i 间：金额为 dp[i-2] + nums[i-1]。
  4. 最终答案为 dp[n]（或 max(dp)，但 dp 是非递减的）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(nums[i-1] + dp[i-2], dp[i-1])
        return max(dp)  # 等价于 dp[n]

📊 性能分析

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)，可优化到 O(1)O(1)（滚动变量）。

思考

该动态规划解法是打家劫舍问题的标准模板。用户代码使用了长度为 n+1 的数组，下标从 1 开始，便于理解。最后返回 max(dp) 虽然正确（因为 dp 单调递增），但直接返回 dp[n] 更高效。也可以使用两个变量滚动，将空间优化到常数级。整体思路清晰，适合初学者。