[Algorithm] House Robber III

House Robber III

Problem statement

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "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:

     3
    / \
   2   3
    \   \ 
     3   1

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

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

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

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Solution: DFS + DP

At each node the maximum amount we can rob is determined by whether we want to rob the current house or skip this house. To keep the constraint that two connected house cannot be robbed, we can utilize post order DFS. In post order DFS we just need to check one side of the constraint which is current house and its immediate children. The other side which is between immediate parent and this house will be checked when the parent node is visited.

Like other house robbery problem, we keep the maximum loot we can have at each node and we also need to know how much we can get if we skip current house, in other words the dp[i] = max((dp[i] + dp[i-2]), dp[i-1]) state transfer still holds here. Thus we just need to add two return values (as reference), one to represent dp[i-1] and one to represent dp[i-2].

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: int rob(TreeNode* root) { int child = 0, grandchild = 0; postDFS(root, child, grandchild); return max(child, grandchild); } /* * current loot means maximum loot starting at this node, * it can come from either taking this node or skiping this node whichever is larger */ void postDFS(TreeNode* root, int& currLoot, int& childLoot) { if (root == NULL) { currLoot = 0; childLoot = 0; return; } int left = 0, leftgrand = 0; postDFS(root->left, left, leftgrand); int right = 0, rightgrand = 0; postDFS(root->right, right, rightgrand); int take = root->val + leftgrand + rightgrand; int skip = left + right; currLoot = max(take, skip); childLoot = skip; } };