算法打卡day41

今日任务：

1）198.打家劫舍

2）213.打家劫舍II

3）337.打家劫舍III

4）复习day16

198.打家劫舍

题目链接：198. 打家劫舍 - 力扣（LeetCode）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 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。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 400

文章讲解：代码随想录 (programmercarl.com)

视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍哔哩哔哩bilibili

思路：

这个问题是一个典型的动态规划问题。我们可以使用动态规划来解决这个问题，其中关键是定义状态和状态转移方程。

状态定义：
定义一个数组 dp，其中 dp[i] 表示偷窃前 i 个房屋所能获取的最高金额。

状态转移方程：
考虑偷窃第 i 个房屋，有两种情况：

偷窃第 i 个房屋：如果偷窃第 i 个房屋，则不能偷窃第 i-1 个房屋，因此偷窃金额为 nums[i] + dp[i-2]。
不偷窃第 i 个房屋：如果不偷窃第 i 个房屋，则偷窃金额与偷窃前 i-1 个房屋所能获取的最高金额相同，即 dp[i-1]。

因此，动态转移方程为：

$dp[i] = max(dp[i-1], dp[i-2] + nums[i])$

初始状态：

第一个房屋只有一间，因此偷窃它即可，即 dp[0] = nums[0]。
第二个房屋偷窃与不偷窃中选择金额较大的方案，即 dp[1] = max(nums[0], nums[1])。

返回结果：
最终结果为 dp[-1]，表示偷窃前所有房屋所能获取的最高金额。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:  # 如果没有房屋，返回0
            return 0
        if len(nums) == 1:  # 如果只有一个房屋，返回其金额
            return nums[0]

        # 定义动态规划数组，dp[i] 表示偷窃前 i 个房屋所能获取的最高金额
        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]

213.打家劫舍II

题目链接：213. 打家劫舍 II - 力扣（LeetCode）

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：
输入：nums = [0]
输出：0

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

文章讲解：代码随想录 (programmercarl.com)

视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II哔哩哔哩bilibili

思路：

这个问题与之前的类似，但有一个额外的条件：房屋围成一圈。因此，我们需要特殊处理这个情况。

我们可以将这个问题拆分成两个子问题：

偷窃第一个房屋，不偷窃最后一个房屋。
偷窃最后一个房屋，不偷窃第一个房屋。

然后，我们可以使用动态规划来解决这两个子问题，最后取两个子问题中的最大值作为结果。

具体的动态规划解决方案如下：
对于第一个子问题，我们可以使用与之前类似的动态规划方法来解决。假设 dp1[i] 表示偷窃前 i 个房屋（第一个房屋被偷窃）所能获取的最高金额，则有以下状态转移方程：
dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]) 其中 dp1[0] = nums[0],dp1[1] = max(nums[0], nums[1])
对于第二个子问题，同样使用动态规划方法。假设 dp2[i] 表示偷窃前 i 个房屋（最后一个房屋被偷窃）所能获取的最高金额，则有以下状态转移方程：
dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i]) 其中 dp2[0] = 0，dp2[1] = nums[1]
最终，我们可以将两个子问题的最终结果进行比较，取其中较大的值作为最终结果。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:  # 如果没有房屋，返回0
            return 0
        if len(nums) == 1:  # 如果只有一个房屋，返回其金额
            return nums[0]

        # 计算偷窃第一个房屋，不偷窃最后一个房屋的最高金额
        res1 = self.rob_range(nums,0,len(nums)-2)
        # 计算偷窃最后一个房屋，不偷窃第一个房屋的最高金额
        res2 = self.rob_range(nums,1,len(nums)-1)

        # 取两个子问题的最大值作为最终结果
        return max(res1,res2)


    # 动态规划解决子问题
    def rob_range(self,nums: List[int], start: int, end: int) -> int:
        if end == start:
            return nums[start]

        # 创建一个数组用于存储每个房屋偷窃时的最高金额
        dp = [0]*(end-start+1)
        # 初始化前两个房屋的最高金额
        dp[0] = nums[start]
        dp[1] = max(nums[start],nums[start+1])

        for i in range(2, end - start + 1):
            # 在偷窃当前房屋和不偷窃当前房屋之间选择金额较大的方案
            dp[i] = max(dp[i-1],dp[i-2]+nums[start+i])

        return dp[-1]

337.打家劫舍III

题目链接：337. 打家劫舍 III - 力扣（LeetCode）

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：
树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

文章讲解：代码随想录 (programmercarl.com)

视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3哔哩哔哩bilibili

思路：

在这个问题中，我们有一棵二叉树，表示小偷可以盗取的房屋。每个节点表示一个房屋，节点的值表示房屋内的现金。树中的相邻节点表示相邻的房屋，如果相邻的房屋在同一晚上被打劫，系统会自动报警。

我们的目标是计算在不触发警报的情况下，小偷一晚能够盗取的最高金额。

解决这个问题的一种方法是使用动态规划。我们可以定义一个递归函数rob(root)，其中 root 是当前节点。对于每个节点，我们有两种选择：

盗取当前节点和其孙子节点的价值，然后考虑其孙子节点的左右孩子。
不盗取当前节点，而是考虑其两个子节点。

我们可以通过递归地计算这两种选择来获得最大金额。但是，这样的方法可能会导致大量的重复计算。为了避免这种情况，我们可以使用记忆化搜索或动态规划来优化递归解法。在动态规划方法中，我们可以定义一个状态数组 dp，其中 dp[node] 表示盗取以 node 为根节点的子树所能获得的最大金额。然后，我们可以根据状态转移方程来计算 dp[node]。

具体地，对于每个节点 node，我们有两种选择：

如果我们盗取了当前节点 node，则不能盗取其孩子节点。因此，最大金额为 node.val + dp[node.left.left] + dp[node.left.right] + dp[node.right.left] + dp[node.right.right]。
如果我们不盗取当前节点 node，则可以选择盗取其左孩子和右孩子。因此，最大金额为 dp[node.left] + dp[node.right]。

最后，我们返回根节点的最大金额，即 dp[root]。

这样，我们可以通过动态规划来高效地解决这个问题，确保小偷在不触发警报的情况下，一晚能够盗取的最高金额。

# 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:
        # 调用辅助函数并返回根节点的最大金额
        return max(self.dfs(root))

    # 定义一个辅助函数来计算盗取以root为根节点的子树所能获得的最大金额
    def dfs(self, node):
        if not node:
            return 0, 0  # 返回不盗取当前节点和盗取当前节点的最大金额

        # 递归计算左右子树的最大金额
        left_no_rob, left_rob = self.dfs(node.left)
        right_no_rob, right_rob = self.dfs(node.right)

        # 不盗取当前节点时，可以选择盗取左右子树的根节点或者不盗取左右子树的根节点
        no_rob = max(left_no_rob, left_rob) + max(right_no_rob, right_rob)

        # 盗取当前节点时，不能盗取左右子树的根节点
        rob = node.val + left_no_rob + right_no_rob

        return no_rob, rob


root = TreeNode(3,2,3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)

obj = Solution()

print(obj.rob(root))

感想：这题有点变化，用到了二叉树，这里要先算子节点的最大值，再算父节点，所以这题要采用后序遍历。