0213. 打家劫舍 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 环形 DP

1. 📝 题目描述

• leetcode

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 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

---

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

2. 🎯 s.1 - 环形 DP

c

int robRange(int* nums, int lo, int hi) {
    int prev = 0, curr = 0;
    for (int i = lo; i <= hi; i++) {
        int temp = curr > prev + nums[i] ? curr : prev + nums[i];
        prev = curr;
        curr = temp;
    }
    return curr;
}

int rob(int* nums, int numsSize) {
    if (numsSize == 1) return nums[0];
    int a = robRange(nums, 0, numsSize - 2);
    int b = robRange(nums, 1, numsSize - 1);
    return a > b ? a : b;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length
  if (n === 1) return nums[0]
  function robRange(lo, hi) {
    let prev = 0,
      curr = 0
    for (let i = lo; i <= hi; i++) {
      const temp = Math.max(curr, prev + nums[i])
      prev = curr
      curr = temp
    }
    return curr
  }
  return Math.max(robRange(0, n - 2), robRange(1, n - 1))
}

py

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        def rob_range(lo, hi):
            prev, curr = 0, 0
            for i in range(lo, hi + 1):
                prev, curr = curr, max(curr, prev + nums[i])
            return curr
        return max(rob_range(0, len(nums) - 2), rob_range(1, len(nums) - 1))

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 环形排列意味着第一个和最后一个不能同时选择
• 分两次计算：范围 $[0,n-2]$ 和 $[1,n-1]$，取两者最大值
• 每次计算等价于经典打家劫舍问题，用两个变量滚动更新