刷题使我快乐,满脸开心.jpg

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/house-robber-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

思路

这道题跟之前的 LeetCode-198. 打家劫舍 非常类似,思路依然是动态规划,三要素这里就不再重复了,可以移步看下原来那篇~

关键点在于,本次的房间是呈一个环形,选择了第一家则不能选择最后一家。

下面我来重点说明下环形带来的两个思考:

固定某个值来继续计算是否可行?

  • 假如固定了 偷第一家,那么其实相应的 最后一家第二家 都不可以偷,所以需要再计算 nums[2:len(nums)-1] 中能偷到的最大值,此时就变成了 LeetCode-198 题目中的问题了
  • 当固定 不偷第一家 时,那就可以直接忽略 第一家,因为这个放弃而解开了首尾相连,所以直接计算 nums[1:] 的最大值即可

不固定某个值来计算是否可行?

不固定某个值其实想法是直接放弃掉某个值从而解开首尾相连,让问题回归到已有思路,基于便利选择第一个值或者最后一个值。

但问题是,这么操作是否可行:

  • 不偷 第一家 时,此时我们并不能确定是否 偷最后一家 ,但是结果集中肯定包含了 偷最后一家 的情况。
  • 偷最后一家 时同理,肯定包含了 偷第一家 的情况。
  • 基于上面的情况分析,其实可以肯定的是,无论如何选择,所有结果集都是能够覆盖到的,所以此思路也是可行的

我对于这道题的思考就是这样了,直接上代码,结合注释看更加清晰~

代码

固定第一家方法

func rob(nums []int) int {
    // 因为下标操作更多,所以对于特殊情况做一些处理
	if len(nums) == 1 {
		return nums[0]
	} else if len(nums) == 2 {
        return max(nums[0], nums[1])
    }
	// 分两种情况,固定偷第一家 和 不偷第一家
	return max(getMax(nums[2:len(nums)-1])+nums[0], getMax(nums[1:]))
}

func getMax(nums []int) int {
    if len(nums) == 0 {return 0}
	// 先用数组,看是否可以滚动数组优化
	// dp[0] 为不偷当前家的最大值
	// dp[1] 为偷当前家的最大值
	dp := make([]int, 2)

	// 初始化
	dp[1] = nums[0]

	// 状态转移方程
	for i := 1; i < len(nums); i++ {
		temp := dp[0]
		// 特殊逻辑,如果0偷了,则不偷当前家
		dp[0] = max(temp, dp[1])
		dp[1] = max(temp+nums[i], dp[1])
	}
	return max(dp[0], dp[1])
}

不固定方法

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
	// 直接拆分两个数组分别放弃一家,求最大值汇总
	return max(getMax(nums[:len(nums)-1]), getMax(nums[1:]))
}

func getMax(nums []int) int {
	// 先用数组,看是否可以滚动数组优化
	// dp[0] 为不偷当前家的最大值
	// dp[1] 为偷当前家的最大值
	dp := make([]int, 2)

	// 初始化
	dp[1] = nums[0]

	// 状态转移方程
	for i := 1; i < len(nums); i++ {
		temp := dp[0]
		// 特殊逻辑,如果0偷了,则不偷当前家
		dp[0] = max(temp, dp[1])
		dp[1] = max(temp+nums[i], dp[1])
	}
	return max(dp[0], dp[1])
}