题目

题目来源：力扣（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 = [0]
输出：0

思路分析

动态规划

这道题是「198. 打家劫舍」的进阶，和第 198 题的不同之处是，这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。

我们分三种情况进行讨论：

  • 情况一：只有一间房屋

在这种情况下，只能偷窃这一间房屋，可以偷窃到最高总金额

  • 情况二：只有两间房屋

由于两间房屋相邻，因此不能同时偷窃，只能偷窃其中金额较高的一间房屋，可以偷窃到最高总金额

  • 情况三：房屋数量超过两间

房屋数量超过两间时，我们必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。因此我们需要分成两种情况来讨论：

1、不偷窃最后一间房屋，那么问题转化为偷窃 1 号 到 i - 1 号房屋所能获得的最高总金额
image.png

2、不偷窃第一间房屋，那么问题转化为偷窃 2 号到 i 号房屋所能获得的最高总金额
image.png

两种情况中取最大值，这样我们就把环状排列问题转化为了两个单排排列的子问题。

我们定义两个数组 f[] 和 g[]：
其中用 f[n - 1] 来表示不偷窃最后一间房屋，偷窃 1号到 n - 1 号房屋所偷窃到的最高总金额，
用 g[n] 表示不偷窃第一间房屋，偷窃 2号 到 i 号房屋所偷窃到的最高总金额
image.png

状态初始化

f[1] = nums[0]，只偷窃1号房屋所能获得的最高金额为 nums[0]
g[2] = nums[1]，把第二间房间当成房间单排排列的起点，只偷窃2号房间所能获得的最高金额为nums[1]

实现细节

我们定义的状态表示f[]、g[]数组以及nums[]数组下标均是从1开始的，而题目给出的nums[]数组下标是从0开始的。为了一 一对应，状态转移方程中的nums[i]的值要往前错一位，取nums[i - 1]。

代码实现

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function (nums) {
  6.   const n = nums.length;
  7.   if (n == 1) return nums[0];       //只有一间房间，返回nums[0]
  8.   const f = new Array(n + 1).fill(0)
  9.   const g = new Array(n + 1).fill(0)
  10.   f[1] = nums[0], g[2] = nums[1];  //初始化
  11.   for (let i = 2; i <= n - 1; i++) {
  12.     f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]); //区间[1,n-1]最大值
  13.   } 
  14.   for (let i = 3; i <= n; i++) {
  15.     g[i] = Math.max(g[i - 1], g[i - 2] + nums[i - 1]); //区间[2,n]最大值
  16.   }      
  17.   return Math.max(f[n - 1], g[n]);
  18. }

二维数组解法

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function (nums) {
  6.   let n = nums.length;
  7.   if (n == 1) return nums[0];//如果只有一个房子也可以偷
  8.   const dp = new Array(n).fill(0).map(v => new Array(2).fill(0));
  9.   // 先求不偷最后一间屋子的最大价值
  10.   dp[0][0] = 0,//不偷就是0
  11.     dp[0][1] = nums[0];//第i间房子偷的最大价值
  12.   for (let i = 1; i < n; i++) {
  13.     dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);//不偷当前房间，那么前一间屋子可偷可不偷
  14.     dp[i][1] = dp[i - 1][0] + nums[i];//偷当前房间，那么前一间房间就不能偷；前一间房间不偷的最大价值 + 当前房子
  15.   }
  16.   // 记录第一个最大值：不偷最后一间获得的最大值
  17.   let ans1 = dp[n - 1][0];
  18.   // 规定：不偷第一间屋子
  19.   dp[0][0] = 0;
  20.   dp[0][1] = 0;//不管第一间房子偷或者不偷，都让小偷无功而返
  21.   for (let i = 1; i < n; i++) {
  22.     dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);
  23.     dp[i][1] = dp[i - 1][0] + nums[i];
  24.   }
  25.   // 到这，第一件房子没偷，所以最后一件房子可以偷/也可以不偷，所以获取在最后一间房子偷或者不偷的最大值
  26.   let ans2 = Math.max(dp[n - 1][0], dp[n - 1][1]);
  27.   return Math.max(ans1, ans2);
  28. };

考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function (nums) {
  6.   const length = nums.length;
  7.   if (length === 1) {
  8.     return nums[0];
  9.   } else if (length === 2) {
  10.     return Math.max(nums[0], nums[1]);
  11.   }
  12.   return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
  13. };
  15. const robRange = (nums, start, end) => {
  16.   let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
  17.   for (let i = start + 2; i <= end; i++) {
  18.     const temp = second;
  19.     second = Math.max(first + nums[i], second);
  20.     first = temp;
  21.   }
  22.   return second;
  23. }