【代码随想录训练营】【Day 50】【动态规划-9】| Leetcode 198, 213, 337

【代码随想录训练营】【Day 50】【动态规划-9】【需二刷】| Leetcode 198, 213, 337

需强化知识点

• 需二刷，打家劫舍系列

题目

198. 打家劫舍

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        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-2]+nums[i], dp[i-1])
        
        return dp[len(nums)-1]


1
2
3
4
5
6
7
8
9
10
11
12
13
14

213. 打家劫舍 II

• 环形问题的拆解：拆解为多种情况，分别计算，取最大值

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

        result = max(self.robRange(nums_v1), self.robRange(nums_v2))
        return result
    
    def robRange(self, nums):
        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[len(nums)-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

337. 打家劫舍 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:
        # if root is None:
        #     return 0
        # if root.left is None and root.right is None:
        #     return root.val
        
        # # 偷父节点
        # val1 = root.val
        # if root.left:
        #     val1 += self.rob(root.left.left) + self.rob(root.left.right)
        # if root.right:
        #     val1 += self.rob(root.right.left) + self.rob(root.right.right)
        
        # # 不偷父节点
        # val2 = self.rob(root.left) + self.rob(root.right)
        # return max(val1, val2)

        dp = self.traversal(root)
        return max(dp)
    
    # 使用后序遍历，因为要通过递归函数的返回值来做下一步计算
    def traversal(self, node):
        if not node:
            return (0, 0)
        
        left = self.traversal(node.left)
        right = self.traversal(node.right)

        # 不偷当前节点，偷子节点
        val_0 = max(left[0], left[1]) + max(right[0], right[1])

        # 偷当前节点，不偷子节点
        val_1 = node.val + left[0] + right[0]

        return (val_0, val_1)
          
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43