leetcode动态规划—打家劫舍系列

lc198 打家劫舍

对于房屋i，考虑偷与不偷

偷i：dp[i-2] + nums[i]

不偷i ：dp[i-1]

class Solution:
    def rob(self, nums: List[int]) -> int:
        #dp[i]: 考虑编号【0-i】房间，偷取的最大金额为dp[i]
        #dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        #求解dp[n-1]
        n = len(nums)
        if n < 2:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[n-1]

lc213 打家劫舍II

拆分为两种情况

考虑头，不考虑尾

考虑尾，不考虑头

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

lc337 打家劫舍III

动态规划法

每层用一个dp数组来存储状态

层与层的状态转移依赖返回值决定，因此是后序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        #dp[0] 不偷父节点得到的最大金额
        #dp[1] 偷父节点得到的最大金额
        def post_traversal(node):
            if not node:
                return (0, 0)
            
            dp_left = post_traversal(node.left)
            dp_right = post_traversal(node.right)

            #偷父节点, 不偷左右孩子
            val1 = node.val + dp_left[0] + dp_right[0]

            #不偷父节点，可考虑左右孩子
            val0 = max(dp_left[0], dp_left[1]) + max(dp_right[0], dp_right[1])
            return (val0, val1)

        return max(post_traversal(root)[0], post_traversal(root)[1])

记忆递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        used_map = {}
        def post_traversal(node):
            if not node:
                return 0
            if used_map.get(node) is not None:
                return used_map[node]

            #偷父节点 不考虑左右孩子
            val1 = node.val
            if node.left:
                val1 += post_traversal(node.left.left) + post_traversal(node.left.right)
            if node.right:
                val1 += post_traversal(node.right.left) + post_traversal(node.right.right)

            #不偷父节点, 考虑左右孩子
            val2 = post_traversal(node.left) + post_traversal(node.right)
            res = max(val1, val2)
            used_map[node] = res
            return res

        return post_traversal(root)