【代码随想录训练营】【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]

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 resultdef 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]

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)