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

**Day48: 打家劫舍系列**

在 LeetCode 上，存在三个与 "打家劫舍" 相关的问题：198、213 和337。这些问题都涉及到一个抢劫者想要抢劫一系列房屋，而每个房屋可能有不同的价值和限制。

###1. 打家劫舍 (198)

**描述**

给定 `n` 个房屋，每个房屋中有 `v[i]` 的价值。抢劫者可以选择在不超过两间房屋中的任意一间进行抢劫。目标是最大化抢劫者的总价值。

**示例1**

输入：`nums = [2,7,9,3,1]`
输出：`10`

**示例2**

输入：`nums = [2,1,1,1,0]`
输出：`4`

**解决方案**

我们可以使用动态规划来解决这个问题。假设 `dp[i]` 表示在第 `i` 个房屋之前的最大价值。

def rob(nums):
 if not nums:
 return0 # Base case: 只有一个房屋 if len(nums) ==1:
 return nums[0]
 # Base case: 有两个房屋 if len(nums) ==2:
 return max(nums[0], nums[1])
 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[-1]

# 测试print(rob([2,7,9,3,1])) # Output:10print(rob([2,1,1,1,0])) # Output:4

###2. 打家劫舍 II (213)

**描述**

给定 `n` 个房屋，每个房屋中有 `v[i]` 的价值。抢劫者可以选择在不超过两间房屋中的任意一间进行抢劫。但是，如果第一个房屋和最后一个房屋不能同时被抢劫，则必须至少有一间房屋不被抢劫。

**示例1**

输入：`nums = [2,3,2]`
输出：`3`

**示例2**

输入：`nums = [10,20,30,40,50]`
输出：`120`

**解决方案**

我们可以使用动态规划来解决这个问题。假设 `dp[i]` 表示在第 `i` 个房屋之前的最大价值。

def rob2(nums):
 if not nums:
 return0 # Base case: 只有一个房屋 if len(nums) ==1:
 return nums[0]
 # Base case: 有两个房屋 if len(nums) ==2:
 return max(nums[0], nums[1])
 dp = [0] * len(nums)
 dp[0] = nums[0]
 dp[1] = max(nums[0], nums[1])
 # 动态规划 for i in range(2, len(nums)-1):
 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
 # 最后一个房屋的价值 last_house_value = max(dp[-2], dp[-3] + nums[-2])
 return last_house_value# 测试print(rob2([2,3,2])) # Output:3print(rob2([10,20,30,40,50])) # Output:120

###3. 打家劫舍 III (337)

**描述**

给定一个二叉树，每个节点有一个 `val` 值。假设每个节点的值代表该节点所能抢劫到的最大价值。如果两个相邻的节点不能同时被抢劫，则必须至少有一间房屋不被抢劫。

**示例1**

输入：`root = [3,2,3,null,4]`
输出：`9`

**示例2**

输入：`root = [3,8,10,1,3,null,null,15]`
输出：`22`

**解决方案**

我们可以使用后序遍历来解决这个问题。假设 `res` 表示最大价值。

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef rob(root):
 if not root:
 return0 # 后序遍历 def postorder(node):
 if not node:
 return [0,0]
 left_values = postorder(node.left)
 right_values = postorder(node.right)
 # 不抢劫当前节点的价值 no_rob_current_node_value = max(left_values[0], left_values[1]) + max(right_values[0], right_values[1])
 # 抢劫当前节点的价值 rob_current_node_value = node.val + left_values[1] + right_values[1]
 return [no_rob_current_node_value, rob_current_node_value]
 values = postorder(root)
 return max(values[0], values[1])

# 测试root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

print(rob(root)) # Output:9root = TreeNode(3)
root.left = TreeNode(8)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.right.left = TreeNode(15)

print(rob(root)) # Output:22

以上是打家劫舍系列问题的解决方案。这些问题都涉及到一个抢劫者想要抢劫一系列房屋，而每个房屋可能有不同的价值和限制。我们使用动态规划和后序遍历来解决这些问题。