线性动态规划：打家劫舍 II 题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。这些房屋围成一个环形，即第一间房屋和最后一间房屋相邻。每个房屋内都藏有一定的现金，但你不能同时偷窃相邻的房屋（包括首尾相邻）。给定一个代表每个房屋金额的非负整数数组，计算你今晚能偷窃到的最高金额。 示例 输入： [2, 3, 2] 输出： 3 解释：不能偷窃相邻的房屋，且首尾相邻，因此只能偷窃第2间房屋（金额为3）。 解题思路 由于房屋围成环形，首尾不能同时偷窃，可将问题拆分为两个线性动态规划子问题： 忽略最后一间房屋 ：偷窃范围是第1间到第n-1间（即 nums[0] 到 nums[n-2] ）。 忽略第一间房屋 ：偷窃范围是第2间到第n间（即 nums[1] 到 nums[n-1] ）。 最终结果为两个子问题的最大值。 步骤分解 定义状态 设 dp[i] 表示偷窃到第i间房屋时的最大金额。 状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i]) ，表示选择不偷第i间（继承 dp[i-1] ）或偷第i间（加上 nums[i] 但跳过 i-1 ）。 处理环形限制 子问题1：计算 nums[0:n-1] 的最大金额。 子问题2：计算 nums[1:n] 的最大金额。 边界情况 若只有一间房屋（ n=1 ），直接返回 nums[0] 。 若有两间房屋（ n=2 ），返回 max(nums[0], nums[1]) （因首尾相邻，只能偷一间）。 动态规划实现 使用滚动变量优化空间复杂度至O(1)： 维护 prev （ dp[i-2] ）和 curr （ dp[i-1] ）。 遍历时更新： next = max(curr, prev + nums[i]) ，然后 prev = curr , curr = next 。 示例演算 输入： nums = [1, 2, 3, 1] 子问题1（忽略最后一间）： [1, 2, 3] 初始： prev = 1 , curr = max(1, 2) = 2 i=2： next = max(2, 1+3) = 4 → prev=2 , curr=4 结果：4 子问题2（忽略第一间）： [2, 3, 1] 初始： prev = 2 , curr = max(2, 3) = 3 i=2： next = max(3, 2+1) = 3 → prev=3 , curr=3 结果：3 最终结果： max(4, 3) = 4 复杂度分析 时间复杂度：O(n)，遍历数组两次。 空间复杂度：O(1)，仅用常数变量存储状态。