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

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

一、打家劫舍

此題為leetcode??第198題??

思路：設(shè)狀態(tài)dp[i]的含義是到第i家時所偷竊到的最高金額。如果偷竊第i家，那么第i – 1家肯定沒有被偷竊，偷竊的金額只能是第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題??

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

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é)點不打劫時得到最多的錢，res[1]代表當(dāng)前節(jié)點打劫獲得最多的錢
        res = [0, 0]
        # 當(dāng)前節(jié)點不打劫時，孩子節(jié)點可以打劫也可以不打劫，最多的錢為左右孩子最多的錢加起來
        # max(左孩子不打劫時獲得最多的錢，左孩子打劫時獲得最多的錢) 
        # + max(右孩子不打劫時獲得最多的錢，右孩子打劫時獲得最多的錢)
        res[0] = max(left[0], left[1]) + max(right[0], right[1])
        # 當(dāng)前節(jié)點打劫時，孩子節(jié)點不可以打劫
        # 左孩子不打劫時獲得最多的錢 + 右孩子不打劫時獲得最多的錢 + 當(dāng)前節(jié)點的錢
        res[1] = left[0] + right[0] + root.val

        return res