学习目标

198.打家劫舍
213.打家劫舍II
337.打家劫舍III

学习内容

198.打家劫舍

198. 打家劫舍 - 力扣（LeetCode）https://leetcode.cn/problems/house-robber/

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)dp = [0]*(n+1)dp[1] = nums[0]for i in range(2,n+1):dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])return dp[n]

213.打家劫舍II

213. 打家劫舍 II - 力扣（LeetCode）https://leetcode.cn/problems/house-robber-ii/

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n==1:return nums[0]@cachedef dfs(i,first):if i<0:return 0if i==0:if first:return nums[i]return 0return max(dfs(i-1,first),dfs(i-2,first)+nums[i])return max(dfs(n-1,False),dfs(n-2,True))

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n==1:return nums[0]dp = [0]*(n+1)dp[1] = nums[0] # 选首家不选尾家for i in range(2,n):dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])a = dp[n-1]dp = [0]*(n+1)for i in range(2,n+1):dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])b = dp[n]return max(a,b)

337.打家劫舍III

337. 打家劫舍 III - 力扣（LeetCode）https://leetcode.cn/problems/house-robber-iii/

# 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:@cachedef dfs(root,robbed):if not root:return 0if robbed:return dfs(root.left,False)+dfs(root.right,False)+root.valreturn max(dfs(root.left,False),dfs(root.left,True))+max(dfs(root.right,False),dfs(root.right,True))return max(dfs(root,False),dfs(root,True))

# 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:@cachedef dfs(root):if not root:return [0,0] # 偷，不偷left = dfs(root.left)right = dfs(root.right)steal = max(left[0],left[1])+max(right[0],right[1])return [left[1]+right[1]+root.val,steal]res = dfs(root)return max(res[0],res[1])