代码随性训练营第四十八天（Python）｜ 198.打家劫舍、213.打家劫舍II、337.打家劫舍 III

198.打家劫舍
1、动态规划

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp 数组代表在第 i 个房间可以偷窃到的最高金额为 dp[i]
        dp = [0] * len(nums)
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0], nums[1])
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[-1]

2、优化版

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre_max = 0 # 上一个房间的最大值
        cur_max = 0 # 当前房间的最大值
        for num in nums:
            tmp = cur_max
            cur_max = max(pre_max + num, cur_max)
            pre_max = tmp
        return cur_max

213.打家劫舍II

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

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

337.打家劫舍 III

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        # dp 数组的含义代表
        # 0 代表偷当前节点获取的最大利益
        # 1 代表不偷当前节点获取的最大利益
        dp = self.traversal(root)
        return max(dp)

    def traversal(self, root):
        if root is None:
            return (0, 0)

        leftdp = self.traversal(root.left)
        rightdp = self.traversal(root.right)

        # 偷当前节点
        val0 = root.val + leftdp[1] + rightdp[1]

        # 不偷当前节点
        val1 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1])

        return (val0, val1)