LeetCode 213. House Robber 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 = [1,2,3] 输出：3解题思路
方法：动态规划
思路：
- 由于房屋围成一圈，第一个房屋和最后一个房屋不能同时偷窃
- 因此，我们可以将问题分解为两个子问题：
- 不偷窃第一个房屋，只考虑从第二个房屋到最后一个房屋的最大金额
- 不偷窃最后一个房屋，只考虑从第一个房屋到倒数第二个房屋的最大金额
- 最终结果为这两个子问题的最大值
- 对于每个子问题，我们可以使用与打家劫舍 I 相同的动态规划方法
复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组两次。
- 空间复杂度：O(1)，只需要常数级的额外空间。
代码实现
方法：动态规划
class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 if n == 1: return nums[0] if n == 2: return max(nums[0], nums[1]) # 辅助函数，计算从 start 到 end 的最大金额 def rob_range(start, end): prev1 = 0 # 对应 dp[i-1] prev2 = 0 # 对应 dp[i-2] for i in range(start, end + 1): current = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = current return prev1 # 子问题 1：不偷窃第一个房屋，只考虑从第二个房屋到最后一个房屋 sub1 = rob_range(1, n-1) # 子问题 2：不偷窃最后一个房屋，只考虑从第一个房屋到倒数第二个房屋 sub2 = rob_range(0, n-2) return max(sub1, sub2)测试用例
测试用例 1：
输入：nums = [2,3,2]
输出：3
测试用例 2：
输入：nums = [1,2,3,1]
输出：4
测试用例 3：
输入：nums = [1,2,3]
输出：3
测试用例 4：
输入：nums = [0]
输出：0
总结
本题是打家劫舍问题的变种，主要考察对动态规划的理解和应用。由于房屋围成一圈，我们需要将问题分解为两个子问题，分别计算不偷窃第一个房屋和不偷窃最后一个房屋的情况，然后取最大值。
动态规划的核心思想是：通过分解问题，将复杂的环形问题转化为两个线性问题，然后使用与打家劫舍 I 相同的方法解决每个子问题。
这种方法不仅适用于打家劫舍 II 问题，还可以应用于许多其他需要分解问题的场景。掌握动态规划的思想，对于解决这类问题非常重要。
