数据结构与算法——高智商犯罪之打家劫舍
2021-12-01 23:04:47

题目以偷东西为背景，但偷东西肯定是违法的，我们千万不能用动态规划去偷东西，用什么算法都不可以，程序员虽然苦逼但这是正当行业，哪怕去摆地摊啊，让我们一起抵制偷窃，共建社会主义和谐社会

一、打家劫舍

此题为leetcode​​第198题​​

思路：设状态dp[i]的含义是到第i家时所偷窃到的最高金额。如果偷窃第i家，那么第i – 1家肯定没有被偷窃，偷窃的金额只能是第i-2家加上第i家的。如果不偷窃第i家，那么第i-1家肯定被偷窃了，当前偷窃的金额就是第i-1家。状态转移方程为：

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题​​

思路：房屋围成一圈的意思是，第一家和最后一家不能都打劫了。分为两种情况：打第一家不打最后一家、打最后一家不打第一家，两种情况的结果取最大值。

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题​​

思路：此题的房子排列是树状的，可以考虑用深度优先搜索。如果在当前节点没有打劫，那么当前的最大利润为左子树最大利润加右子树最大利润；如果当前节点被打劫，那么最大利润为左子树不打劫时的最大利润加右子树不打劫时最大利润再加当前节点的金额。因此在DFS递归的时候，每层递归用一个数res1表示当前节点不打劫所获最大利润，res2表示当前节点打劫所获最大利润，并返回。最终结果为两个中最大的一个。

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]代表当前节点不打劫时得到最多的钱，res[1]代表当前节点打劫获得最多的钱
        res = [0, 0]
        # 当前节点不打劫时，孩子节点可以打劫也可以不打劫，最多的钱为左右孩子最多的钱加起来
        # max(左孩子不打劫时获得最多的钱，左孩子打劫时获得最多的钱) 
        # + max(右孩子不打劫时获得最多的钱，右孩子打劫时获得最多的钱)
        res[0] = max(left[0], left[1]) + max(right[0], right[1])
        # 当前节点打劫时，孩子节点不可以打劫
        # 左孩子不打劫时获得最多的钱 + 右孩子不打劫时获得最多的钱 + 当前节点的钱
        res[1] = left[0] + right[0] + root.val

        return res