华为 OD 训练营 · 题解精讲
LC213. 打家劫舍II
LC213. 打家劫舍II
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 示例 1： 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。 示例 2： 输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 3： 输入：nums = [0] 输出：0 提示： 1 <= nums.length <= 100 0 <= nums[i] <= 1000
题目解析
解题思路
本题是“打家劫舍”的环形版本，核心难点在于首尾房间不能同时被偷。参考代码采用分类讨论策略，将环形问题拆解为两个线性子问题：要么不偷第一个房间（考虑下标1到n-1），要么不偷最后一个房间（考虑下标0到n-2）。最终答案取这两个子问题结果的最大值。
算法与数据结构：动态规划（DP），使用一维数组value记录前i个房间能偷到的最大金额。
关键步骤
1. 边界处理：若数组长度n<=1，直接返回对应值。 2. 拆分数组：生成两个子数组——nums[1:]（排除第一个房间）和nums[:-1]（排除最后一个房间）。 3. 调用线性DP函数myRob：
- 初始化
value[0]=0，value[1]=nums[0]。 - 从
i=2到n，状态转移方程：
value[i] = max(value[i-1], value[i-2] + nums[i-1])- 含义：当前房间i-1要么不偷（继承
value[i-1]），要么偷（加上value[i-2]）。
4. 取最大值：返回两个子问题结果中的较大值。
示意图（以nums=[1,2,3,1]为例）：
情况1（排除首房）：[2,3,1] → DP得4
情况2（排除尾房）：[1,2,3] → DP得4
最终结果：max(4,4)=4复杂度分析
- 时间复杂度：O(n)，每个子数组各执行一次线性DP，总遍历次数为2n。
- 空间复杂度：O(n)，DP数组
value长度为n+1。可优化为O(1)（但参考代码未做此优化）。
参考代码
class Solution:
def rob(self, nums):
# 获取房间总数
n = len(nums)
# 如果数组为空，返回0
if n == 0:
return 0
# 如果数组只有一个元素，返回该元素的金额
if n == 1:
return nums[0]
# 不选择第一个房间
nums_except_first_room = nums[1:]
# 不选择最后一个房间
nums_except_last_room = nums[:-1]
# 从这两个选择中挑选出最大值
return max(self.myRob(nums_except_first_room), self.myRob(nums_except_last_room))
def myRob(self, nums):
# 获取房间总数
n = len(nums)
# 创建一个数组value来存放前n个房间可以偷取的最大金额
value = [0] * (n + 1)
# 前0个房间无法偷取，金额为0
value[0] = 0
# 前1个房间只有一个房间可偷取，金额为该房间的金额
value[1] = nums[0]
# 从i = 2到i = n，value中的结果由前i-2和i-1共同决定
for i in range(2, n + 1):
# 转移方程：value[i]等于value[i-1]和value[i-2]+nums[i-1]中的较大值
value[i] = max(value[i - 1], value[i - 2] + nums[i - 1])
# 返回value的最后一个值
return value[n]