House Robber III

描述

All houses in this place forms a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Example 1:

  1.      3
  2.     / \
  3.    2   3
  4.     \   \ 
  5.      3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

  1.      3
  2.     / \
  3.    4   5
  4.   / \   \ 
  5.  1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

分析

树形动规。设状态 f(root) 表示抢劫root为根节点的二叉树，root可抢也可能不抢，能得到的最大金钱，g(root)表示抢劫root为根节点的二叉树，但不抢root，能得到的最大金钱，则状态转移方程为

f(root) = max{f(root.left) + f(root.right), g(root.left)+g(root.right) + root.val}

g(root) = f(root.left) + f(root.right)

代码

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dp/house-robber-iii.html