lt198 打家劫舍I
[1,2,3,1] 相邻不能偷
dp 记录最大
func rob(nums []int) int {
n:=len(nums)
//注意边界值，0个返回0，一个返回最初值
if n<=0{
return 0
}
if n==1{
return nums[0]
}
//dp代表到达位置的最大值，前一个和i-2+nums[i]的最大值
dp:=make([]int,len(nums)+1)
dp[0] = nums[0]
dp[1] = max(dp[0],nums[1])
for i:=2;i<n;i++{
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
}
return dp[n-1]
}
func max(x, y int) int{
if x>y{
return x
}else{
return y
}
}
lt213 打家劫舍II
房子头尾相连，相邻不能偷
两个dp分别记录拿第一个房间和不拿第一个
0，1，2时直接返回
func rob(nums []int) int {
if len(nums)==0{
return 0
}
if len(nums)==1{
return nums[0]
}
if len(nums)==2{
return max(nums[0],nums[1])
}
dp:=make([]int,len(nums)+1)
dp2:=make([]int,len(nums)+1)
dp[0] = nums[0]
dp[1] = max(dp[0],nums[1])
dp2[0] = nums[1]
dp2[1] = max(dp2[0],nums[2])
//两个 代表拿第一个和不拿第一个
for i:=2;i<len(nums)-1;i++{
dp[i] = max(dp[i-1],dp[i-2]+nums[i])
dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i+1])
}
return max(dp[len(nums)-2],dp2[len(nums)-2])
}
func max(x,y int)int {
if x>y{
return x
}else{
return y
}
}