# code tpl

{%hackmd theme-dark %}

[ 1 2 3 4 5]

dp[i] = max(dp[i-1], house[i]+dp[i-2])

[1 2 3 4]

[2 3 4 5]


def recur(node):

return rob_this, not_rob_this

TC: O(N)

def rob(houses):
    l = len(houses)

    def helper(subHouses):
        # [1 2 3 4]
        #[2 3 4 5]
        dp = [0]*len(subHouses)
        #[0 0 0 0]
        dp[0] = subHouses[0]
        #[1 0 0 0]
        #[2 0 0 0]
        dp[1] = max(subHouses[0:2]) # h0 or h1
        #[1 2 0 0]
        #[2 3 0 0]
        for i in range(2, len(subHouses)):
            #dp[2] = max(2, 3+1) = 4
            #dp[3] = max(4, 4+2) = 6
            
            #dp[2] = max(3, 4+2) = 6
            #dp[3] = max(4, 5+3) = 8
            dp[i] = max(dp[i-1], subHouses[i]+dp[i-2])
        
        return max(dp) #6 #8
    

                #[1 2 3 4]           #[2 3 4 5]
    return max(helper(houses[:l-1]), helper(houses[1:]))
    
    
    N: house number
    TC: O(2N) -> O(N)
        3
   /        \
  2*(2, 3)   3(3, 1)
 /           |
3*(3, 0)     1(1, 0)
    
    def robTree(root):
        
        def helper(node):
            
            if not node:
                return 0, 0
            
            lRob, lNotRob = helper(node.left)# 2 3
            rRob, rNotRob = helper(node.right)# 3 1
            
            robThis = node.val + lNotRob + rNotRob # 3+3+1
            notRobThis = max(lRob, lNotRob) + max(rRob, rNotRob) #3 + 3
            
            return robThis, notRobThis # 7, 6

        robRoot, notRobRoot = helper(root)
        return max(robRoot, notRobRoot) # 7
        
    N: house node
    TC: O(N)

###### tags: `mock interview` `面試`