星尘

动态规划总结-打家劫舍

发表于 更新于 分类于 ，

打家劫舍

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

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

示例：输入：[1,2,3,1]，输出：4

示例：输入：[2,7,9,3,1]，输出：12，解释：2 + 9 + 1 = 12

  • dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
  • 如果偷第i房间，那么 dp[i] = dp[i - 2] + nums[i] 即：如果第 i 天偷，那么 i-1 天肯定不偷，那么就是 第 i-2 天偷，目前偷得的最大价值为 dp[i - 2] + nums[i]
  • 如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1
  • 要取偷与不偷的最大值 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  • dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])
  • dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:  # 如果没有房屋，返回0
            return 0
        if len(nums) == 1:  # 如果只有一个房屋，返回其金额
            return nums[0]

        # 创建一个动态规划数组，用于存储最大金额
        dp = [0] * len(nums)
        dp[0] = nums[0]  # 将dp的第一个元素设置为第一个房屋的金额
        dp[1] = max(nums[0], nums[1])  # 将dp的第二个元素设置为第一二个房屋中的金额较大者

        # 遍历剩余的房屋
        for i in range(2, len(nums)):
            # 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[-1]  # 返回最后一个房屋中可抢劫的最大金额

打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

示例, 输入：nums = [2,3,2], 输出：3。输入：nums = [1,2,3,1], 输出：4

  • 这里和上一题的区别在于，本题要考虑是否成环。如果不成环的话，那么有三种情况。
    1. 只考虑排除了第一个元素和最后一个元素的列表
    2. 考虑包含首元素，不包含尾元素的列表
    3. 考虑包含尾元素，不包含首元素的列表
  • 情况2 和 情况3 都包含了情况1了，所以只考虑情况二和情况三就可以了
  • 剩下的和上题一样了，只需把情况2和情况3的值求出，然后取一个最大值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums):
            return 0
        if len(nums.size()) == 1:
            return nums[0]
        
        result1 = self.robRange(nums, 0, len(nums) - 2)  # 情况二
        result2 = self.robRange(nums, 1, len(nums) - 1)  # 情况三
        # 取两种情况的最值
        return max(result1, result2)
		
    # 和上题 打家劫舍 逻辑一样
    def robRange(self, nums, start, end) -> int:
        if start == end:
            return nums[start]

        dp = [0] * len(nums)
        dp[start] = nums[start]
        dp[start + 1] = max(nums[start], nums[start + 1])

        # 上面已经处理了 dp[start] 和 dp[start+1]，所以这里从 start + 2 开始处理
        for i in range(start + 2, end):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[end]

打家劫舍 III

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

  • 本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。
  • dp数组是一个二维数组：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
  • 在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
  • 如果是偷当前节点，那么左右孩子就不能偷。val1 = cur->val + left[0] + right[0]
  • 如果不偷当前节点，那么左右孩子就可以偷，确定偷，那么一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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:
        # dp数组（dp table）以及下标的含义：
        # 1. 下标为 0 记录 不偷该节点  所得到的的最大金钱
        # 2. 下标为 1 记录 偷该节点   所得到的的最大金钱
        dp = self.traversal(root)
        return max(dp)

    # 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
    def traversal(self, node):
        
        # 递归终止条件，就是遇到了空节点，那肯定是不偷的
        if not node:
            return (0, 0)

        left = self.traversal(node.left)     # 后序遍历，左右中
        right = self.traversal(node.right)

        # 不偷当前节点, 偷子节点
        val_0 = max(left[0], left[1]) + max(right[0], right[1])

        # 偷当前节点, 不偷子节点
        val_1 = node.val + left[0] + right[0]

        return (val_0, val_1)