边工作边刷题：70天一遍leetcode: day 92

House Robber I/II/III

这题代表了单向线性dp的基本pattern: build local best value at each element and track the global optimal. 这题的要点是local是前k个房间的最优解，这个解不一定要选第k个房间。这个local解是比较k-1的optimal和k-2 optimal + current value。之所以不以必选第k个房间作local是因为有可能最优解有连续2或多个房间不选，比如100，1，1，100

III:

• binary tree和array的思路是一样的，对于当前root，需要前面两层的结果：left/right subtree的max和left/right的子树的max
• 同时，和array一样，返回的值不是必然包括root的
• 在计算left/right子树的max时，只需要sum，因为root对于两层后只关心sum

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        pre_2 = nums[0]
        if len(nums)<2: return pre_2
        pre_1 = max(nums[0],nums[1])
        cur = pre_1
        for i in range(2, len(nums)):
            cur = max(pre_1, pre_2+nums[i])
            pre_2=pre_1
            pre_1=cur
        
        return cur
        

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def robOneDir(nums):
            pre_1 = nums[0]
            pre_2 = max(nums[0], nums[1])
            for i in range(2, len(nums)):
                cur = max(pre_2, pre_1+nums[i])
                pre_1=pre_2
                pre_2=cur
            return pre_2
        
        if not nums: return 0
        if len(nums)<2: return nums[0]
        if len(nums)==2: return max(nums[0], nums[1])
        nums1,nums2=nums[0:-1],nums[1:]
        return max(robOneDir(nums1), robOneDir(nums2))

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def robRec(root):
            pre_left_1,pre_left_2,pre_right_1,pre_right_2=0,0,0,0
            if root.left:
                pre_left_1, pre_left_2 = robRec(root.left)
                
            if root.right:
                pre_right_1, pre_right_2 = robRec(root.right)
                
            cur = max(pre_left_2+root.val+pre_right_2, pre_left_1+pre_right_1)
            return cur, pre_left_1+pre_right_1
            
        if not root: return 0
        maxValue, noUse = robRec(root)
        return maxValue