你提到的 198. House Robber 是 LeetCode 上的一道经典动态规划题目。下面我给你详细讲解题意、思路，并提供 Python 实现代码。
🔹题目描述
你是一个专业的小偷，计划沿街盗窃每家屋子里的钱。每个屋子都有一定的现金，唯一的限制是：
- 相邻的屋子不能同时偷（因为有警报系统）。
目标：计算你能偷窃到的 最大金额。
输入：nums = [2,7,9,3,1]
输出：12 （偷第 1 个和第 3 个和第 5 个屋子，或者第 2 个和第 4 个）
🔹思路分析
这是 动态规划（DP） 问题。
设：
dp[i]表示到第 i 个屋子为止能偷的最大金额。
状态转移方程：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
含义：
- 不偷第 i 个 → 最大值就是
dp[i-1] - 偷第 i 个 → 就不能偷 i-1，收益为
dp[i-2] + nums[i]
初始条件：
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
🔹Python 实现
class Solution:
def rob(self, nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
🔹优化空间（只用两个变量）
因为状态转移只依赖 dp[i-1] 和 dp[i-2]，所以可以优化为 O(1) 空间：
class Solution:
def rob(self, nums):
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr
✅ 时间复杂度：O(n)
✅ 空间复杂度：O(1)
好嘞 👍 阿杰，我来帮你整理一整套 House Robber 系列题解（I、II、III），包含思路 + 图解 + Python 代码，这样你毕设或者刷题的时候直接能用。
🏠 House Robber 系列题解合集
198. House Robber I
题意： 一排房子，每间房子有金额，不能偷相邻的两间，求最大收益。
状态转移：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
代码：
class Solution:
def rob(self, nums):
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr
213. House Robber II
题意： 房子变成了环形，首尾相邻，仍然不能偷相邻的。
思路：
- 环形 = 两种情况：
- 偷第 0 间，不偷最后一间 → 范围
[0, n-2] - 偷最后一间，不偷第 0 间 → 范围
[1, n-1]
- 偷第 0 间，不偷最后一间 → 范围
- 答案 = 两种情况的最大值
代码：
class Solution:
def rob(self, nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
def rob_line(houses):
prev, curr = 0, 0
for h in houses:
prev, curr = curr, max(curr, prev + h)
return curr
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
337. House Robber III
题意： 房子变成了 二叉树，相邻定义为父子关系，不能同时偷父子。
思路：
- 用 DFS，递归时返回两个值：
rob_this= 偷当前节点（= 当前值 + 左右子树不偷的收益）not_rob_this= 不偷当前节点（= 左右子树最大收益）
代码：
class Solution:
def rob(self, root):
def dfs(node):
if not node:
return (0, 0) # (偷当前，不偷当前)
left = dfs(node.left)
right = dfs(node.right)
rob_this = node.val + left[1] + right[1]
not_rob_this = max(left) + max(right)
return (rob_this, not_rob_this)
return max(dfs(root))
📌 总结
- House Robber I：线性 DP。
- House Robber II：环形 DP → 分两次线性 DP。
- House Robber III：树形 DP → DFS 返回 (偷，不偷)。
时间复杂度：
- I、II：O(n)
- III：O(n)，n 是树节点数
好的阿杰 😊 我来给你整理 LeetCode 198. House Robber（打家劫舍） 的完整学习资料，包括：题目解析 → 动态规划思路 → Python/Java代码 → 复杂度分析。
🔹 题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房子都有一定金额的现金，但相邻的房子有 安全系统，如果同一晚上偷了相邻两间房子，就会报警。
求 在不触动警报的情况下，你能偷窃到的最高金额。
输入：nums = [2,7,9,3,1]
输出：12
解释：偷第 1、3、5 号房子 → 2 + 9 + 1 = 12
🔹 思路讲解
这是一道 动态规划 DP 经典题。
1. 状态定义
dp[i]表示 前 i 个房子能偷到的最大金额。
2. 转移方程
对于第 i 个房子，有两种选择：
- 不偷第 i 个房子：
dp[i] = dp[i-1] - 偷第 i 个房子：
dp[i] = dp[i-2] + nums[i]
所以：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 初始条件
dp[0] = nums[0]dp[1] = max(nums[0], nums[1])
🔹 Python 解法
class Solution:
def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
# 测试
print(Solution().rob([2,7,9,3,1])) # 输出 12
🔹 Java 解法
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.length - 1];
}
}
🔹 优化空间复杂度
注意 dp[i] 只依赖前两个状态，可以用 两个变量滚动更新，节省 O(n) → O(1) 空间。
Python 优化版
class Solution:
def rob(self, nums):
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr
Java 优化版
class Solution {
public int rob(int[] nums) {
int prev = 0, curr = 0;
for (int num : nums) {
int temp = curr;
curr = Math.max(curr, prev + num);
prev = temp;
}
return curr;
}
}
🔹 复杂度分析
- 时间复杂度：O(n)，遍历一次数组
- 空间复杂度：O(1)，使用滚动变量优化后
发表回复