动态规划题解_打家劫舍【LeetCode】-EW帮帮网

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 。

这个问题的核心思想是动态规划。我们可以将问题分解为子问题：

对于每个房子 i，我们有两种选择：偷或不偷。

如果我们偷了第 i 个房子，那么我们不能偷第 i-1 个房子，所以最大金额是 dfs(i - 2) + nums[i]。

如果我们不偷第 i 个房子，那么最大金额是 dfs(i - 1)。

我们取这两种选择中的最大值作为 dfs(i) 的结果。

下面关于这道题目的具体题解，思路和之前的爬楼梯题目解题思路一致，建议先看完这篇文档再来继续食用哦~~

动态规划题解——爬楼梯【LeetCode】三种方法_动态规划爬楼梯-CSDN博客

一、算法逻辑（每一步思路）

❓ 问题描述：

给定一个整数数组 nums，每个元素表示某一间房屋中的金额。相邻的房屋不能被同时偷盗，问最多可以偷多少钱。

✅ 解题思路（DP 状态定义与转移）

1. 状态定义：

设：

f0 表示「不偷当前这家时的最大收益」；
f1 表示「偷当前这家时的最大收益」。

随着遍历每一间房，我们动态更新这两个变量。

2. 状态转移逻辑：

对于当前房屋金额 x：

如果我们偷它，就不能偷上一个：f1 = f0 + x
如果我们不偷它，就保留上一个偷的最大值：f1 = max(f1, f0 + x)
所以前一步状态要滚动更新：先将 f0 = f1，然后用前一个 f0 + x 计算新的 f1

总结起来为：

f0, f1 = f1, max(f1, f0 + x)

3. 初始化：

初始时 f0 = f1 = 0，表示没偷任何房屋；
随着每个房间的遍历进行动态更新。

4. 最终返回结果：

f1 就是最终的最大收益（在遍历结束后，无论最后一间偷还是不偷都已被计算）。

二、算法核心点

✅ 核心思想：动态规划 + 状态滚动

对于每一间房子都有两种选择：偷或不偷；
关键是不能偷相邻的两家，因此形成状态递推结构；
用两个变量 f0、f1 取代整个数组，进行滚动优化。

class Solution:
    def rob(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

三、复杂度分析

时间复杂度：O(n)

- 遍历数组一遍。

空间复杂度：O(1)

- 只用了两个变量（而不是数组），空间极致优化。

总结表

维度	内容
✅ 思路逻辑	每间房子选择“偷”或“不偷”，根据前一个状态递推最大金额
✅ 核心技巧	动态规划 + 状态滚动优化（用 f0, f1 代替 dp 数组）
✅ 时间复杂度	O(n)
✅ 空间复杂度	O(1)

✅ 举个例子说明

输入：

nums = [2, 7, 9, 3, 1]

状态变化：

初始: f0 = 0, f1 = 0
遍历 2: f0 = 0, f1 = max(0, 0 + 2) = 2
遍历 7: f0 = 2, f1 = max(2, 0 + 7) = 7
遍历 9: f0 = 7, f1 = max(7, 2 + 9) = 11
遍历 3: f0 = 11, f1 = max(11, 7 + 3) = 11
遍历 1: f0 = 11, f1 = max(11, 11 + 1) = 12

最终返回 f1 = 12

动态规划题解_打家劫舍【LeetCode】