golang刷leetcode：BM79 打家劫舍(二)
golang刷leetcode：BM79 打家劫舍(二)
golangLeetcode
发布于 2022-12-17 16:14:04
发布于 2022-12-17 16:14:04
文章被收录于专栏：golang算法架构leetcode技术php
描述
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
示例1
输入：
[1,2,3,4]复制
返回值：
6复制
说明：
最优方案是偷第 2 4 个房间示例2
输入：
[1,3,6]复制
返回值：
6复制
说明：
由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间解题思路：
1，本题是个环形的，所以比较难处理
2，其实可以拆成两个子问题
A，抢劫第一家，不抢劫最后一家
B，抢劫最后一家，不抢劫第一家
3，拆成这两个子问题后，剩余的就是简单的第一种情况了,状态转移方程为：
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
4,依赖两个值，可以降维度优化
代码实现：
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
func rob( nums []int ) int {
// write code here
switch len(nums){
case 0:
return 0
case 1:
return nums[1]
case 2:
if nums[0]>nums[1]{
return nums[0]
}
return nums[1]
default:
}
dp:=[2]int{nums[0],nums[1]}
if nums[0]>nums[1]{
dp[1]=nums[0]
}
start:=getDp(nums,dp,len(nums)-1)
end:=getDp(nums,[2]int{0,nums[1]},len(nums))
if start<end{
return end
}
return start
}
func getDp(nums []int,dp [2]int ,end int)int{
for i:=2;i<end;i++{
tmp:=dp[1]
if dp[0]+nums[i]>dp[1]{
dp[1]=dp[0]+nums[i]
}
dp[0]=tmp
}
return dp[1]
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-08-13，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
