每日一题-2020805

题目

打家劫舍

题解

动态规划，主要是找到子问题。每个节点都有选择与不选择两种情况，记选择为 f，不选择为。

选择父节点，则不能选择该节点的孩子节点。则最优解为 f(o) = g(l) + g(r)
不选择该节点，则可以选择孩子节点，孩子节点同样有两种情况，取 Max(f(l), g(l)) + Max(f(r), g(r))

object steal {

  case class TreeNode(var value:Int, var left: TreeNode, var right:TreeNode)

  def rob(root: TreeNode): Int = {
    var f = Map[TreeNode, Int]()
    var g = Map[TreeNode, Int]()


    def dfs(node:TreeNode):Unit = {
      if (node == null) {
        return
      }
      dfs(node.left)
      dfs(node.right)
      val fl = f.getOrElse(node.left, 0)
      val fr = f.getOrElse(node.right, 0)
      val gl = g.getOrElse(node.left, 0)
      val gr = g.getOrElse(node.right, 0)
      f = f + (node -> (node.value + gl + gr))
      g = g + (node -> (scala.math.max(fl, gl) +  scala.math.max(fr, gr)))

    }
    dfs(root)
    scala.math.max(f.getOrElse(root, 0), g.getOrElse(root, 0))
  }

  def main(args: Array[String]): Unit = {
    val tree = TreeNode(3, TreeNode(3, null, null), TreeNode(4, TreeNode(4, null, null), null))

    println(rob(tree))
  }

}