3.13 LeetCode House Robber

题目

给定一个数组nums，代表每家可以打劫到的钱数，连着打劫相邻的两家会自动报警。在保证不报警的前提下，找到可以打劫到的最多钱数。

思路

一开始想，分别奇偶索引求和，最后输出大的，不对，例如[2,1,1,2]，取首尾最大。
使用动态规划的思想，到达第i家能获得的最大收益（不一定能打劫）是，max( gain[i-1], gain[i-2] + nums[i] )，不一定要维护整个数组，只需保留最后两个值。

代码

   # 思路错，[2,1,1,2]，不一定奇偶间隔取最大。
    odd = 0
    even = 0
    for i in range(len(nums)):
        if i & 0x001 == 1:
            odd += nums[i]
        else:
            even += nums[i]
    return max(odd,even)

    # 正确的解法，不维护整个数组，只需保留最后两个值
    last = 0
    now = 0
    for i in nums:
        temp = now
        now = max(now, last+i)
        last = temp
    return now

    # 另一种直观的写法
    if not nums: return 0
    if len(nums) == 1: return nums[0]
        
    dp = [[0] for _ in range(len(nums))]
    
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        # rob this house or the previous one
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

进阶1

该题在House Robber的基础上让首位链接形成环，那么即表示第一个和最后一个不能同时被抢，则问题分解为House Robber（nums[0:len(nums)-1]）和House Robber（nums[1:len(nums)]），两者中比较大的那个即为结果

代码

    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0], nums[1])
        return max(self.dfs(nums[:-1]), self.dfs(nums[1:]))
    
    def dfs(self, nums):
        if len(nums) == 2:
            return max(nums[0], nums[1])
        gain = [0 for _ in nums]
        gain[0] = nums[0]
        gain[1] = max(nums[0], nums[1])
        for i in range(2,len(nums)):
            gain[i] = max(gain[i-1], gain[i-2]+nums[i])
        return gain[-1]

进阶2

小偷又发现一个新的可行窃的地点。 这个地区只有一个入口，称为“根”。 除了根部之外，每栋房子有且只有一个父房子。 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋形成了一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

在不触动警报的情况下，计算小偷一晚能盗取的最高金额。

思路

遍历二叉树用递归，
递归关系：如何从rob(root.left)，rob(root.right)等等获取rob(root)。
从树根的角度来看，最后只有两个场景：根被抢劫或没有被抢劫。
如果root被抢劫，此时的收获为root的值，加上左右节点不被抢的值
如果root不被抢劫，此时的收获为左右节点能收获的最大值之和（注意此时不一定要抢左右节点，因为没有限制，哪个大就选哪个）。
我们只需要选择产生更多金钱的场景。
递归终止条件：根节点为空，注意因为要传递两个参数，因此返回[0, 0]

代码

    def rob(self, root: TreeNode) -> int:
        return max(self.treerob(root))
    def treerob(self, root):
        if root == None:
            return [0]*2
        gain = [0]*2
        left = self.treerob(root.left)
        right = self.treerob(root.right)
        gain[0] = max(left) + max(right) # 不偷root
        gain[1] = root.val + left[0] + right[0]
        return gain