數(shù)據(jù)結(jié)構(gòu)與算法——高智商犯罪之打家劫舍
2021-12-01 23:04:47

題目以偷東西為背景，但偷東西肯定是違法的，我們千萬(wàn)不能用動(dòng)態(tài)規(guī)劃去偷東西，用什么算法都不可以，程序員雖然苦逼但這是正當(dāng)行業(yè)，哪怕去擺地?cái)偘?，讓我們一起抵制偷竊，共建社會(huì)主義和諧社會(huì)

一、打家劫舍

此題為leetcode??第198題??

思路：設(shè)狀態(tài)dp[i]的含義是到第i家時(shí)所偷竊到的最高金額。如果偷竊第i家，那么第i – 1家肯定沒(méi)有被偷竊，偷竊的金額只能是第i-2家加上第i家的。如果不偷竊第i家，那么第i-1家肯定被偷竊了，當(dāng)前偷竊的金額就是第i-1家。狀態(tài)轉(zhuǎn)移方程為：

d p [ i ] = m a x ( d p [ i ? 2 ] + n u m s [ i ] , d p [ i ? 1 ] ) dp[i]=max(dp[i-2]+nums[i], dp[i-1]) dp[i]=max(dp[i?2]+nums[i],dp[i?1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) <= 2:
            return max(nums)
        dp = [0] * len(nums)
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return dp[-1]

二、打家劫舍II

此題為leetcode??第213題??

思路：房屋圍成一圈的意思是，第一家和最后一家不能都打劫了。分為兩種情況：打第一家不打最后一家、打最后一家不打第一家，兩種情況的結(jié)果取最大值。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) <= 2:
            return max(nums)

        def my_rob(nums):
            dp = [0] * len(nums)
            dp[0], dp[1] = nums[0], max(nums[0], nums[1])
            for i in range(2, len(nums)):
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
            return dp[-1]

        return max(my_rob(nums[1:]), my_rob(nums[:-1]))

三、打家劫舍III

此題為leetcode??第337題??

思路：此題的房子排列是樹(shù)狀的，可以考慮用深度優(yōu)先搜索。如果在當(dāng)前節(jié)點(diǎn)沒(méi)有打劫，那么當(dāng)前的最大利潤(rùn)為左子樹(shù)最大利潤(rùn)加右子樹(shù)最大利潤(rùn)；如果當(dāng)前節(jié)點(diǎn)被打劫，那么最大利潤(rùn)為左子樹(shù)不打劫時(shí)的最大利潤(rùn)加右子樹(shù)不打劫時(shí)最大利潤(rùn)再加當(dāng)前節(jié)點(diǎn)的金額。因此在DFS遞歸的時(shí)候，每層遞歸用一個(gè)數(shù)res1表示當(dāng)前節(jié)點(diǎn)不打劫所獲最大利潤(rùn)，res2表示當(dāng)前節(jié)點(diǎn)打劫所獲最大利潤(rùn)，并返回。最終結(jié)果為兩個(gè)中最大的一個(gè)。

class Solution:
    def rob(self, root: TreeNode) -> int:
        res = self.dfs(root)
        return max(res)

    def DFS(self, root):
        if root is None:
            return [0, 0]

        left = self.DFS(root.left)      # 遞歸左孩子
        right = self.DFS(root.right)    # 遞歸右孩子

        # res[0]代表當(dāng)前節(jié)點(diǎn)不打劫時(shí)得到最多的錢(qián)，res[1]代表當(dāng)前節(jié)點(diǎn)打劫獲得最多的錢(qián)
        res = [0, 0]
        # 當(dāng)前節(jié)點(diǎn)不打劫時(shí)，孩子節(jié)點(diǎn)可以打劫也可以不打劫，最多的錢(qián)為左右孩子最多的錢(qián)加起來(lái)
        # max(左孩子不打劫時(shí)獲得最多的錢(qián)，左孩子打劫時(shí)獲得最多的錢(qián)) 
        # + max(右孩子不打劫時(shí)獲得最多的錢(qián)，右孩子打劫時(shí)獲得最多的錢(qián))
        res[0] = max(left[0], left[1]) + max(right[0], right[1])
        # 當(dāng)前節(jié)點(diǎn)打劫時(shí)，孩子節(jié)點(diǎn)不可以打劫
        # 左孩子不打劫時(shí)獲得最多的錢(qián) + 右孩子不打劫時(shí)獲得最多的錢(qián) + 當(dāng)前節(jié)點(diǎn)的錢(qián)
        res[1] = left[0] + right[0] + root.val

        return res