readme.md

You are a professional robber planning to rob houses along a street.

Each house has a certain amount of money stashed.

Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

q1: max robbery ?

q2: what if houses form a circle so the first and last are neighbors ?

q3: what if houses form a binary tree ?

rob.js

const rob = function(nums) {
        if (!nums)  return 0 
          
        let prev1 = prev2 = 0 
        
        for (num of nums){
             [prev1, prev2] = [Math.max(prev2+num, prev1), prev1]
        }
           
        return prev1
};

rob_circular.py

def rob_circular(self, nums: List[int]) -> int:
    def rob_linear(nums):
        if not nums:
            return 0 

        prev1 = prev2 = 0 

        for num in nums:
            prev1, prev2 = max(prev2+num, prev1), prev1

        return prev1

    n = len(nums)
    if n==0:
        return 0
    if n==1:
        return nums[0]

    return max(rob_linear(nums[:n-1]), rob_linear(nums[1:n]))

rob_linear.go

func max(a int,b int) int{
    if a>b{
        return a
    }
    return b 
}

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    p1, p2 := 0, 0 
    for _, num := range(nums) {
        p1 , p2 = max(p2+num, p1), p1
    } 
    
    return p1 
}

rob_linear.py

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0 

    def decide(i):
        if i<2:
            return max(nums[:i+1])
        if i not in dp:
            rob = decide(i-2) + nums[i]
            skip = decide(i-1)
            dp[i] = max(rob, skip)
        return dp[i]

    dp = {}
    n = len(nums)
    return decide(n-1)

rob_linear2.py

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0 

    prev1 = prev2 = 0 

    for num in nums:
        prev1, prev2 = max(prev2+num, prev1), prev1

    return prev1

robTree.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type pair struct {
    now int
    later int
}

func max(a int, b int) int{
    if a > b {
        return a
    }
    return b 
}

func robTree(node *TreeNode) pair {
    /*
    now: max money earned if input node is robbed
    later: max money earned if input node is not robbed
    */
    if node == nil {
        return pair{}
    }

    left := robTree(node.Left)
    right := robTree(node.Right)
    
    p := pair{}
    p.now = node.Val + left.later + right.later
    p.later = max(left.now, left.later) + max(right.now, right.later)

    return p
    
}

func rob(root *TreeNode) int {    
    if root == nil {
        return 0
    }
    res := robTree(root)
    return max(res.now, res.later)
}

robTree.py

def rob(self, root: TreeNode) -> int:

    def robTree(node):
        """
        now: max money earned if input node is robbed
        later: max money earned if input node is not robbed
        """
        if not node: return 0,0

        left,right = robTree(node.left), robTree(node.right)

        now = node.val + left[1] + right[1]

        later = max(left) + max(right)

        return now, later

    res = robTree(root)

    return max(res)