刷题使我快乐,满脸开心.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])
}