337.打家劫舍III

337.打家劫舍III

题解

题目：给一个二叉树，相邻两个节点不能同时选，问能选的节点累加最大的值

思路：
暴力递归 - 最优子结构

1.既然相邻不能选，那么
method1：选当前节点以及4个孙子节点
method2：不选当前节点，选两个孩子节点
返回max(method1, method2)

记忆化 - 解决重复子问题

爷爷节点会计算孙子节点
父节点也会计算孙子节点
存在重复子问题，用记忆化解决

动态规划

即使用了记忆化剪枝，还是会超时，所以只能用动态规划了
选择当前节点：当前节点的值+不选左孩子节点+不选右孩子节点
selected[root] = root.Val + notSelected[root.Left] + notSelected[root.Right]
不选当前节点 = max(选左孩子，不选左孩子)+max(选右孩子，不选右孩子)
notSelected[root] = max(selected[root.Left], notSelected[root.Left]) + max(selected[root.Right], notSelected[root.Right])

优化

我们发现递归回去的时候，无论是selected[root]还是notSelected[root]
他们的状态始终与notSelected[root.Left] ，notSelected[root.Right]，selected[root.Left]，selected[root.Right]
这4个有关
所以我们可以定义一个长为2的数组，arr[0]代表选，arr[1]代表不选
在每次递归的时候返回给上一级，节省空间复杂度

代码

TLE 暴力递归 - 最优子结构

func rob(root *TreeNode) int {if root == nil {return 0}method1 := root.Valif root.Left != nil {method1 += rob(root.Left.Left) + rob(root.Left.Right)}if root.Right != nil {method1 += rob(root.Right.Left) + rob(root.Right.Right)}method2 := rob(root.Left) + rob(root.Right)return max(method1, method2)
}
func max(i, j int) int {if i > j {return i}return j
}

TLE 记忆化 - 解决重复子问题

func rob(root *TreeNode) int {mp := map[*TreeNode]int{}var dfs func(root *TreeNode) intdfs = func(root *TreeNode) int {if _, ok := mp[root]; ok {return mp[root]}if root == nil {return 0}method1 := root.Valif root.Left != nil {method1 += rob(root.Left.Left) + rob(root.Left.Right)}if root.Right != nil {method1 += rob(root.Right.Left) + rob(root.Right.Right)}method2 := rob(root.Left) + rob(root.Right)mp[root] = max(method1, method2)return mp[root]}return dfs(root)
}
func max(i, j int) int {if i > j {return i}return j
}

动态规划

func rob(root *TreeNode) int {selected := map[*TreeNode]int{}notSelected := map[*TreeNode]int{}var dfs func(root *TreeNode)dfs = func(root *TreeNode) {if root == nil {return}dfs(root.Left)dfs(root.Right)selected[root] = root.Val + notSelected[root.Left] + notSelected[root.Right]notSelected[root] = max(selected[root.Left], notSelected[root.Left]) + max(selected[root.Right], notSelected[root.Right])}dfs(root)return max(selected[root], notSelected[root])
}
func max(i, j int) int {if i > j {return i}return j
}

动态规划-优化

func rob(root *TreeNode) int {var dfs func(root *TreeNode) [2]intdfs = func(root *TreeNode) [2]int { //0选 1不选if root == nil {return [2]int{0, 0}}l := dfs(root.Left)r := dfs(root.Right)selected := root.Val + l[1] + r[1]notSelected := max(l[0], l[1]) + max(r[0], r[1])return [2]int{selected, notSelected}}val := dfs(root)return max(val[0], val[1])
}
func max(i, j int) int {if i > j {return i}return j
}