golang力扣leetcode 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]代表不选
在每次递归的时候返回给上一级，节省空间复杂度

func rob(root *TreeNode) int {
  if root == nil {
    return 0
  }
  method1 := root.Val
  if 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
}

func rob(root *TreeNode) int {
  mp := map[*TreeNode]int{}
  var dfs func(root *TreeNode) int
  dfs = func(root *TreeNode) int {
    if _, ok := mp[root]; ok {
      return mp[root]
    }
    if root == nil {
      return 0
    }
    method1 := root.Val
    if 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]int
  dfs = 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
}