代码随想录二刷Day48

今日任务

198.打家劫舍
213.打家劫舍II
337.打家劫舍III
语言：Go

198. 打家劫舍

链接：https://leetcode.cn/problems/house-robber/

func max(i, j int) int {if i < j {return j} else {return i}
}func rob(nums []int) int {//dp[i]表示0～i号房屋打劫的金额最大为dp[i]dp := make([]int, len(nums))dp[0] = nums[0]if len(nums) > 1 { //attentiondp[1] = max(nums[0], nums[1])}for i := 2; i < len(nums); i++ {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])}return dp[len(nums) - 1]
}

213. 打家劫舍II

链接：https://leetcode.cn/problems/house-robber-ii/
情况一：不包含首尾元素
情况二：不包含尾元素（偷了第一间屋子就不能偷最后一间屋子了）
情况三：不包含首元素（偷了最后一间屋子就不能偷第一间屋子了）
情况二/三包含了情况一，所以只需要考虑情况二/三

func max(i, j int) int {if i < j {return j} else {return i}
}func robRange(nums []int, start, end int) int {if start == end {return nums[start]}dp := make([]int, len(nums))dp[start] = nums[start]dp[start + 1] = max(nums[start], nums[start + 1])for i := start + 2; i <= end; i++ {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])}return dp[end]
}func rob(nums []int) int {if len(nums) == 1 {return nums[0]}if len(nums) == 2 {return max(nums[0], nums[1])}result1 := robRange(nums, 0, len(nums) - 2)result2 := robRange(nums, 1, len(nums) - 1)return max(result1, result2)
}

337. 打家劫舍III

链接：https://leetcode.cn/problems/house-robber-iii/

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func max(i, j int) int {if i < j {return j} else {return i}
}//dp[0]-不偷当前节点的最高金额
//dp[1]-偷当前节点的最高金额
func robTree(root *TreeNode) [2]int {var dp [2]intif root == nil {dp[0] = 0dp[1] = 0return dp}left := robTree(root.Left)right := robTree(root.Right)//不偷rootdp[0] = max(left[0], left[1]) + max(right[0], right[1])//偷rootdp[1] = root.Val + left[0] + right[0]return dp
}func rob(root *TreeNode) int {dp := robTree(root)return max(dp[0], dp[1])
}