校招算法面试-打家劫舍(二)

本题是经典的动态规划问题，核心在于处理环形数组的限制条件，即首尾元素不能同时选取。以下是详细的解答：

解题思路

问题分析：与线性数组的打家劫舍问题不同，环形数组的首尾相邻增加了复杂性。直接应用原问题的动态规划解法会导致首尾同时被选中的情况，因此需要分情况讨论。
关键观察：环形约束意味着首尾元素不能同时偷。因此，问题可分解为两个子问题：
偷第一家，不偷最后一家：此时问题转化为对数组 nums[0..n-2] 的线性打家劫舍。
不偷第一家，偷最后一家：此时问题转化为对数组 nums[1..n-1] 的线性打家劫舍。
动态规划解法：
状态定义：dp[i] 表示前 i 个房屋能偷到的最大金额。
状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])，即当前房屋的最大金额为“偷当前房屋+前前房屋的最大金额”与“不偷当前房屋，取前房屋的最大金额”中的较大值。
初始条件：dp[0] = 0（无房屋可偷），dp[1] = nums[0]（仅第一家）。
分情况处理：
情况1：包含第一家，排除最后一家。计算 dp[0..n-1]（实际遍历到 n-2）。
情况2：排除第一家，包含最后一家。计算 dp[1..n]（初始 dp[1] = 0，遍历到 n-1）。
结果合并：取两种情况的最大值作为最终结果。

解决代码class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1: return nums[0] def rob_linear(sub_nums): n = len(sub_nums) if n == 0: return 0 dp = [0] * (n + 1) dp[1] = sub_nums[0] for i in range(2, n + 1): dp[i] = max(dp[i-1], dp[i-2] + sub_nums[i-1]) return dp[n] # 情况1：偷第一家，不偷最后一家 case1 = rob_linear(nums[:-1]) # 情况2：不偷第一家，偷最后一家 case2 = rob_linear(nums[1:]) return max(case1, case2)代码解释

边界处理：如果数组为空，返回0；如果只有一家，直接返回该家的金额。
辅助函数 rob_linear：处理线性数组的打家劫舍问题，使用动态规划计算最大金额。
初始化：dp 数组长度为 n+1，dp[1] 初始化为第一家的金额。
状态转移：遍历数组，更新 dp[i] 为“偷当前房屋”或“不偷当前房屋”的较大值。
分情况处理：
情况1：调用 rob_linear 处理 nums[0..n-2]（排除最后一家）。
情况2：调用 rob_linear 处理 nums[1..n-1]（排除第一家）。
返回结果：两种情况的最大值即为所求。

此方法通过分治策略将环形问题转化为两个线性子问题，确保首尾不同时被选中，同时利用动态规划高效求解，时间复杂度为 O(n)，空间复杂度为 O(n)。

您可能感兴趣问答

Collapsible

热门标签

热点问答