198. 打家劫舍（中）
- 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
动态规划
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
# base case
dp[0] = nums[0]#第1间
dp[1] = max(nums[0], nums[1])#第2间
# 状态转移
for i in range(2, n):#从第三间开始
dp[i] = max(dp[i-1], dp[i-2] + nums[i])#当前这间抢不抢，取决于前一家和前前家哪家抢得到的钱多
return dp[n-1]#一直到最后一间
优化
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
prev1 = nums[0] # 前一个房间的最大金额
prev2 = max(nums[0], nums[1]) # 前两个房间的最大金额
for i in range(2, n):
curr = max(prev2, prev1 + nums[i])
prev1, prev2 = prev2, curr
return prev2
213. 打家劫舍Ⅱ（中）
-
所有的房屋都 围成一圈，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。其余条件同上一题
-
思路：只需要在上一题的基础上，选择是第一个房间到倒数第二个获取金额多还是从第二个房间开始到最后一个房间获取的金额多。
动态规划
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
def robrange(nums,start,end):
prev1 = 0 # 前一个房间的最大金额
prev2 = nums[start] # 前两个房间的最大金额
for i in range(start+1, end):
curr = max(prev2, prev1 + nums[i]) # 当前房间的最大金额
prev1, prev2 = prev2, curr # 更新前一个房间和前两个房间的金额
return prev2 # 返回最后一个房间的最大金额
return max(robrange(nums,1,n),robrange(nums,0,n-1)) #取从第二个房间开始到最后一个房间，与，从第一个房间开始到倒数第二个房间的最大值
337. 打家劫舍Ⅲ（中）
- 所有的房屋都排成树， 如果两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
示例 1：
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
- 思路：选择：在当前节点加上孙子节点的金额多还是当前节点的两个儿子节点加起来的金额多
动态规划
# 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: TreeNode) -> int:
memo = {} # 备忘录，用于存储已经计算过的子问题的结果
def robTree(node):
if not node:
return 0
if node in memo: # 如果该节点已经计算过，直接返回结果，避免重复计算
return memo[node]
rob_left = robTree(node.left.left) + robTree(node.left.right) if node.left else 0 # 打劫当前节点的左子树的子节点的最大金额
rob_right = robTree(node.right.left) + robTree(node.right.right) if node.right else 0 # 打劫当前节点的右子树的子节点的最大金额
rob_current = node.val + rob_left + rob_right # 打劫当前节点的打劫及当前节点的左子树的子节点和右子树的子节点的最大金额
rob_skip = robTree(node.left) + robTree(node.right) # 不打劫当前节点，打劫左右子树的最大金额
result = max(rob_current, rob_skip) # 取两种情况下的较大值作为结果
memo[node] = result # 将计算结果存储到备忘录中
return result
return robTree(root)