213. 打家劫舍II

题目描述：

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

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

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

---

方法：动态规划

思路：

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

那么，如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？

• 如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；
• 如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

计算方式 198、打家劫舍 一致，唯一的区别是需要分别计算出以上两种情况，然后取较大值即可。

让我们通过一个简单的例子来说明这个思路：

假设给定房屋金额数组 nums = [2, 7, 9, 3, 1]。

1. 需要分为两种情况，即nums1 = [7, 9, 3, 1],nums2 = [2, 7, 9, 3]
2. 通过198、打家劫舍的方法计算出在 nums1 中可偷取的最大金额为second1
3. 通过198、打家劫舍的方法计算出在 nums2 中可偷取的最大金额为second2
4. 最终结果为max(second1,second2)，表示小偷在整个偷取过程中能够获取的的最大金额。

通过这个思路，我们有效地避免了相邻房屋同时被偷窃的情况，最终得到了一夜之内能够偷窃到的最高金额。

func rob(nums []int) int {
	max := func(i, j int) int {
		if i > j {
			return i
		}
		return j
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		return max(nums[0], nums[1])
	}
	var first1, second1 = nums[0], max(nums[0], nums[1])
	var first2, second2 = nums[1], max(nums[1], nums[2])
	for index := 2; index < len(nums); index++ {
		// 不偷取第一家的情况
		if index != 2 {
			first2, second2 = second2, max(nums[index]+first2, second2)
		}
		// 不偷取最后一家的情况
		if index != len(nums)-1 {
			first1, second1 = second1, max(nums[index]+first1, second1)
		}
	}
	return max(second1, second2)
}

复杂度：

• 时间复杂度：O(n)，其中 n 为房屋的数量。只需遍历一次数组。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.9 MB,击败了73.53% 的Go用户