1. 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

  1. 输入：nums = [2,3,2]
  2. 输出：3
  3. 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

  1. 输入：nums = [1,2,3,1]
  2. 输出：4
  3. 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
  4.      偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

  1. 输入：nums = [0]
  2. 输出：0

提示：

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 1000

    2. 解题思路

    打家劫舍这类问题其实都可以使用动态规划来解答，这个题目和打家劫舍类似，不过就是多了两种情况：

  • 不偷第一家

  • 不偷最后一家

这样我们就可以分类讨论，当不偷第一家时，就排除到第一家，对其他家进行计算，当不偷最后一家时，就排除掉最后一家，对其他家进行计算。

当前节点的最大值就是当前节点和之前的第二个节点的和与上个节点的值的最大值，这样说可能比较绕，状态转移方程代码：

  1. dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

复杂度分析：

  • 时间复杂度：O(n)，其中n是数组的长度，我们需要遍历两次数组；

  • 空间复杂度：O(n)，其中n是数组的长度，我们需要初始化一个长度为n的数组来保存当前节点的状态。

    3. 代码实现

    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var rob = function(nums) {
    6.   const len = nums.length
    7.   let res1 = 0, res2 = 0
    8.   if(len === 0) return 0
    9.   if(len === 1) return nums[0]
    11.   const dp = new Array(len)
    13.   // 不偷第一家
    14.   dp[0] = 0
    15.   dp[1] = nums[1]
    16.   for(let i = 2; i <= len - 1; i++){
    17.       dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    18.   }
    19.   res1 = dp[len - 1]
    21.   // 不偷最后一家
    22.   dp[0] = nums[0]
    23.   dp[1] = Math.max(nums[0], nums[1])
    24.   for(let i = 2; i <= len - 2; i++){
    25.       dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    26.   }
    27.   res2 = dp[len - 2]
    28.   return Math.max(res1, res2)
    29. };

    4. 提交结果

    image.png