景安做网站教程,小企业网站制作,如何建设自己的网站 知乎,seo网站优化方案【代码随想录训练营】【Day 50】【动态规划-9】【需二刷】| Leetcode 198, 213, 337
需强化知识点
需二刷#xff0c;打家劫舍系列
题目
198. 打家劫舍
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 1:return nums[0]dp [0] * (len(nums))dp…【代码随想录训练营】【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, val0, leftNone, rightNone):
# 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)
