欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3.13 LeetCode House Robber

程序员文章站 2022-07-12 12:34:35
...

题目

给定一个数组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

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

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

思路

遍历二叉树用递归,
递归关系:如何从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
相关标签: 动态规划

上一篇: 46、47-Permutations

下一篇: Token