337.House Robber III

In [1]:

import sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time, buildtree
from binarytree import build, tree, Node

House Robber III

It will automatically contact the police if two directly-linked houses were broken into on the same night.

In [2]:

null = None
A = [3, 2, 3, null, 3, null, 1]
buildtree(A).pprint()

  __3
 /   \
2     3
 \     \
  3     1

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

DFS search

Note that

• If current node is robbed, both left and right children must not be robbed(skipped).
• If current nodes are not robbed, just merge optimal left and right values(overlapping subproblems).

Let optimal value of a cur(as a root node) of a subtree be $G^*$.

Resursive formula as follows such that

• $*$ means the optimal case.
• $i$ of $G^i$ determines rob the node $i$ or not.
• $G_{left}$ or $G_{right}$ determines the left node or right node. \(\begin{align} G_i^* &= max(G_i^1, G_i^2) \\ G_i^1 &= G_{left}^* + G_{right}^* , \text{where } G_{case} = max(G_{left}^1, G_{right}^2)* \\ G_i^2 &= G_{left}^* + G_{right}^* + i_{val} \\ \end{align}\)

It takes $O(n!)$ because entry $i$ takes $O(i!)$ through recursive call.

In [3]:

class Solution1:
    @logging_time
    def rob(self, root: Node) -> int:
        if not root: return 0
        def dfs(cur, rob:bool) -> int:
            if not cur:
                return 0
            if rob:
                return cur.value + dfs(cur.left, rob=False) + dfs(cur.right, rob=False)
            leftmax = max(dfs(cur.left, rob=True), dfs(cur.left, rob=False))
            rightmax = max(dfs(cur.right, rob=True), dfs(cur.right, rob=False))
            return leftmax + rightmax

        return max(dfs(root, rob=True), dfs(root, rob=False))
sol1 = Solution1()

In [4]:

print(sol1.rob(buildtree(A), verbose=True))

WorkingTime[rob]: 0.11730 ms
7

DFS search + DP

This problem satisfies optimal substructure property, overlapping subproblems.
Therefore, dynamic programming is possible.
Time complexity can be improved as follows: $O(n)$
This is because the number of all entries is $n$, each entry takes $O(1)$.
(recall that $ G_i^* = max(G_i^1, G_i^2)$, just select a $max$ value between first or second cases.)

In [5]:

class Solution2:
    @logging_time
    def rob(self, root:Node) -> int:
        if not root: return 0
        seen = {}
        def dfs(cur, rob:bool) -> int:
            if (cur, rob) in seen:
                return seen[cur, rob]
            if not cur:
                return 0
            if rob:
                seen[(cur, rob)] = cur.value + dfs(cur.left, rob=False) + dfs(cur.right, rob=False)
                return seen[(cur, rob)]
            leftmax = max(dfs(cur.left, rob=True), dfs(cur.left, rob=False))
            rightmax = max(dfs(cur.right, rob=True), dfs(cur.right, rob=False))
            seen[(cur, rob)] = leftmax + rightmax
            return seen[(cur, rob)]

        return max(dfs(root, rob=True), dfs(root, rob=False))
sol2 = Solution2()

In [6]:

print(sol1.rob(buildtree(A) ,verbose=True))
print(sol2.rob(buildtree(A) ,verbose=True))

WorkingTime[rob]: 0.11992 ms
7
WorkingTime[rob]: 0.08249 ms
7

Test using brinarytree module

In [7]:

root = tree(height=9, is_perfect=False)
# root.pprint()
print(len(root.values))
print(sol1.rob(root ,verbose=True))
print(sol2.rob(root, verbose=True))

1012
WorkingTime[rob]: 216.88080 ms
157917
WorkingTime[rob]: 11.42621 ms
157917

Reference

[1] discuss