leetcode198 打家劫舍
一轮循环，确定递归公式即可ac
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0if 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 0if 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 - startif n == 1:return nums[start]dp = [0] * ndp[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 0if 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.valif 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)
