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)

代码

  1. // House Robber III
  2. // Time Complexity: O(n), Space Complexity: O(h)
  3. public class Solution {
  4.     public int rob(TreeNode root) {
  5.         return dfs(root)[0];
  6.     }
  8.     private static int[] dfs(TreeNode root) {
  9.         int[] dp = new int[] {0, 0}; // f, g
  10.         if (root != null) {
  11.             int[] dpL = dfs(root.left);
  12.             int[] dpR = dfs(root.right);
  13.             dp[1] = dpL[0] + dpR[0];
  14.             dp[0] = Math.max(dp[1], dpL[1] + dpR[1] + root.val);
  15.         }
  16.         return dp;
  17.     }
  18. }

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