LeetCode 213. House Robber II 题解

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 问题还可以应用于许多其他需要分解问题的场景。掌握动态规划的思想对于解决这类问题非常重要。