Leetcode-刷题笔记1-动态规划part07
目录
Leetcode 刷题笔记1 动态规划part07
leetcode198 打家劫舍
一轮循环，确定递归公式即可ac
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * (n + 1)
dp[1] = nums[0]
dp[2] = max(nums[0], nums[1])
for i in range(3, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]leetcode 213 打家劫舍 ||
收尾相接考虑三种情况，最后合并为两种情况
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
result1 = self.robRange(nums, 0, len(nums) - 1)
result2 = self.robRange(nums, 1, len(nums))
return max(result1, result2)
def robRange(self, nums: List[int], start, end) -> int:
n = end - start
if n == 1:
return nums[start]
dp = [0] * n
dp[0] = nums[start]
dp[1] = max(nums[start], nums[start + 1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i + start])
return dp[-1]leetcode 打家劫舍|||
带标志位递归（用于减少递归的重复）：
class Solution:
memory = {}
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
if self.memory.get(root) is not None:
return self.memory[root]
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)
self.memory[root] = max(val1, val2)
return max(val1, val2)动态规划：
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
return max(dp := self.traversal(root))
def traversal(self, node):
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
val_0 = node.val + left[0] + right[0]
val_1 = max(left[0], left[1]) + max(right[0], right[1])
return (val_1, val_0)