Python每日一练(20230516) 打家劫舍 I\II\III\IV HouseRobber

今天的Python每日一练是关于打家劫舍的四道题目：HouseRobber IIIIIIIV。这四道题目都是关于在一排房子中选择一些房子进行打劫，但是每道题目都有不同的限制条件和要求。下面我们来逐一解析这四道题目。

HouseRobber I

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房屋都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：

输入: [1231]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

思路：

这道题目可以使用动态规划来解决。我们定义一个数组dp，其中dp[i]表示偷到第i个房子时能够获得的最大金额。那么对于第i个房子，我们有两种选择：偷或者不偷。如果我们选择偷第i个房子，那么我们就不能偷第i-1个房子，所以此时能够获得的最大金额为dp[i-2]+nums[i]。如果我们选择不偷第i个房子，那么此时能够获得的最大金额为dp[i-1]。因此，我们可以得到状态转移方程：dp[i] = max(dp[i-2]+nums[i] dp[i-1])。

代码示例：

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

HouseRobber II

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房屋都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

注意：这道题目与HouseRobber I的区别在于，这里的房屋是围成一圈的，也就是说第一个房子和最后一个房子是相邻的。

示例：

输入: [232]
输出: 3
解释: 偷窃 1 号房屋 (金额 = 2)，然后偷窃 3 号房屋 (金额 = 2)。
偷窃到的最高金额 = 2 + 2 = 4 。

思路：

这道题目可以使用动态规划来解决。我们可以将这个环形的房子拆成两个线性的房子，一个是从第一个房子到倒数第二个房子，另一个是从第二个房子到最后一个房子。对于这两个线性的房子，我们可以使用HouseRobber I中的方法来求解。最后，我们将这两个线性的结果取最大值即可。

代码示例：

class Solution:
def rob(self nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums[0] nums[1])
return max(self.rob_linear(nums[:-1]) self.rob_linear(nums[1:]))

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

HouseRobber III

题目描述：

在一棵二叉树中，每个节点都有一个非负整数的权值，代表该节点可以偷到的钱。同时，每个节点都有两个子节点，如果该节点被偷了，那么它的子节点就不能被偷。求在不触发警报的情况下，能够偷到的最大金额。

示例：

输入: [323null3null1]
3
/
2 3

3 1
输出: 7
解释: 小偷偷窃值为 3 的根节点，然后偷窃值为 3 的右子树节点和值为 1 的右子树节点。
偷窃到的最高金额 = 3 + 3 + 1 = 7 。

思路：

这道题目可以使用递归来解决。对于每个节点，我们有两种选择：偷或者不偷。如果我们选择偷该节点，那么我们就不能偷该节点的左右子节点，所以此时能够获得的最大金额为该节点的权值加上其左右子节点的左右子节点的最大金额。如果我们选择不偷该节点，那么此时能够获得的最大金额为其左右子节点的最大金额之和。因此，我们可以得到状态转移方程：rob(root) = max(val+rob(root.left.left)+rob(root.left.right)+rob(root.right.left)+rob(root.right.right) rob(root.left)+rob(root.right))。

代码示例：

class Solution:
def rob(self root: TreeNode) -> int:
if not root:
return 0
val = 0
if root.left:
val += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val += self.rob(root.right.left) + self.rob(root.right.right)
return max(val+root.val self.rob(root.left)+self.rob(root.right))

HouseRobber IV

题目描述：

在一棵二叉树中，每个节点都有一个非负整数的权值，代表该节点可以偷到的钱。同时，每个节点都有两个子节点，如果该节点被偷了，那么它的子节点就不能被偷。现在，你是一个专业的小偷，计划偷窃这棵二叉树中的一些节点，但是你不能偷相邻的节点。求在不触发警报的情况下，能够偷到的最大金额。

示例：

输入: [34513null1]
3
/