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