线性动态规划：打家劫舍 II（进阶版——环形街道） 题目描述 你是一个专业的小偷，计划偷窃沿环形街道的房屋。每间房屋都存放着一定金额的现金，但所有房屋围成一圈，这意味着第一间房屋和最后一间房屋是相邻的，不能同时偷窃相邻的两间房屋。给定一个代表每个房屋存放金额的非负整数数组 nums ，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 示例 1： 输入：nums = [ 2,3,2 ] 输出：3 解释：因为第一间和最后一间相邻，所以不能同时偷窃它们。最佳选择是偷窃第二间房屋（金额=3）。 示例 2： 输入：nums = [ 1,2,3,1 ] 输出：4 解释：偷窃第一间（金额=1）和第三间（金额=3），总金额=1+3=4。注意，不能偷窃最后一间（金额=1），因为它与第一间相邻。 约束条件： 1 <= nums.length <= 100 0 <= nums[ i] <= 1000 解题思路 这个题目是经典“打家劫舍”问题的进阶版，核心区别在于房屋是环形排列的。在环形排列中，如果偷窃了第一间房屋，就不能偷最后一间；反之，如果偷了最后一间，就不能偷第一间。因此，问题可以转化为两个线性问题的组合，然后取最大值。 步骤拆解 第一步：分析环形结构的处理 由于首尾相邻，我们需要分别考虑两种情况： 偷窃范围从第一间到倒数第二间（即不偷最后一间）。 偷窃范围从第二间到最后一间（即不偷第一间）。 这样就将环形问题拆分成两个线性打家劫舍子问题，每个子问题中房屋是线性排列的，可以直接用经典的动态规划方法求解。 第二步：回顾线性打家劫舍的解法 对于线性排列的房屋，我们用动态规划数组 dp[i] 表示偷窃到第 i 间房屋时能获得的最大金额。状态转移方程为： \[ dp[ i] = \max(dp[ i-1], \ dp[ i-2] + nums[ i ]) \] 解释： 不偷第 i 间，则最大金额等于偷到第 i-1 间的最大金额，即 dp[i-1] 。 偷第 i 间，则不能偷第 i-1 间，最大金额等于偷到第 i-2 间的最大金额加上第 i 间的金额，即 dp[i-2] + nums[i] 。 初始状态： dp[0] = nums[0] （只有一间房屋时，只能偷它）。 dp[1] = max(nums[0], nums[1]) （有两间时，选金额大的偷）。 第三步：将环形问题转化为两个线性问题 定义两个子问题： 子问题 A：偷窃区间 [0, n-2] （排除最后一间）。 子问题 B：偷窃区间 [1, n-1] （排除第一间）。 分别用上述线性动态规划求解两个子问题的最大金额，然后取两者的最大值作为最终答案。 特殊情况处理 ： 如果只有一间房屋（ n == 1 ），那么只能偷这一间，直接返回 nums[0] 。 如果只有两间房屋（ n == 2 ），由于首尾相邻，只能偷其中一间，返回 max(nums[0], nums[1]) 。 第四步：逐步计算示例 以 nums = [1,2,3,1] 为例： 拆分： 子问题 A：区间 [ 0,2]，即 [1,2,3] 。 子问题 B：区间 [ 1,3]，即 [2,3,1] 。 求解子问题 A（线性动态规划）： 初始化： dp[0]=1 , dp[1]=max(1,2)=2 。 计算 dp[2] ： max(dp[1], dp[0]+3) = max(2, 1+3)=4 。 结果为 4。 求解子问题 B（线性动态规划）： 初始化： dp[0]=2 , dp[1]=max(2,3)=3 。 计算 dp[2] ： max(dp[1], dp[0]+1) = max(3, 2+1)=3 。 结果为 3。 最终结果： max(4, 3) = 4 。 第五步：算法复杂度 时间复杂度：O(n)，我们遍历了两次数组（两个子问题各一次）。 空间复杂度：O(1)，实际上只需要用两个变量滚动记录 dp[i-1] 和 dp[i-2] 即可，不需要存储整个 dp 数组。 第六步：总结思路 环形打家劫舍的核心技巧是“化环为线”——通过排除首或尾，将问题转化为两个独立的线性打家劫舍问题。这种拆分方法保证了不会同时偷窃首尾房屋，同时覆盖了所有可能的偷窃方案。