动态规划 打家劫舍

Question Ⅰ🔎

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

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
     
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

Code Ⅰ💡

def house_rob_i(nums: list) -> int:

    # 当无房间时, 直接返回0
    if not nums:
        return 0

    # 只有一个房间时, 那就只能偷它的了
    if len(nums) == 1:
        return nums[0]

    # 设置一个列表, 下标 i 对应着前 i 个房间可以偷取的最大金额
    max_money = [0, nums[0]]

    # 从第2个房间开始计算, 传入第1个房间后的列表
    # 这里需要注意的是, 取 max_money 对应值时, i 要进行加一
    for i, v in enumerate(nums[1:]):
        # max_money[i+1] 表示不偷取当前房间的累计金额
        # max_money[i] + v 表示偷取当前房间的累计金额
        # 对比2种情况, 取最大值追加到 max_money 中
        max_money.append(max(max_money[i+1], max_money[i] + v))

    # 返回最后一个值
    return max_money[-1]

原题地址 -> https://leetcode-cn.com/problems/house-robber/

Test Ⅰ💠

print('house_rob_i')
nums = [1,2,3,1]
print(house_rob_i(nums))
nums = [2,7,9,3,1]
print(house_rob_i(nums))

---

Question Ⅱ🔎

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

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

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

Code Ⅱ💡

def house_rob_ii(nums: list) -> int:
    # 这里只需要在第一题的基础上考虑两种情况
    # 第一种: 包含首元素, 不包含尾元素
    # 第二种: 不包含首元素, 包含尾元素
    # 综上, 一行代码搞定~
    return max(rob_money_i(nums[1:]), rob_money_i(nums[:-1]))

原题地址 -> https://leetcode-cn.com/problems/house-robber-ii/

Test Ⅱ💠

print('house_rob_ii')
nums = [2,3,2]
print(house_rob_ii(nums))
nums = [1,2,3,1]
print(house_rob_ii(nums))

---

Question Ⅲ🔎

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

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

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

Code Ⅲ💡

进阶版来了, 这里考虑的同样是前一个房子和后一个房子是否相隔, 需要考虑的同样只有两种情况, 解题思路是一样的.
但要注意的是, 这是二叉树结构, 这样的话, 每个节点有两种情况, 而每个节点由有两个子节点(我们把空的节点当成0), 既有${2^n}$的可能, 因此采用递归的方式来解决问题会更方便.

def house_rob_iii(root: Optional[TreeNode]) -> int:
    
    # 设置递归函数, 返回偷取当前层和不偷取当前层的钱
    def dfs(node = root) -> tuple:
        
        # 当前节点为空, 当前层和不偷取当前层的钱都为0, 返回(0,0)
        if not node:
            return (0, 0)
        
        # 递归获取左右子树能偷取的金额
        L, R = dfs(node.left), dfs(node.right)
		
        # node.val+(L[1]+R[1]) 表示偷取当前层和下下层的金额
        # max(L)+max(R) 表示当前层不偷,偷取下一层的金额
        return (node.val+(L[1]+R[1]), max(L)+max(R))
	
    # 返回偷第一个房子金额和不偷第一个房子金额的最大值
    return max(dfs())

原题地址 -> https://leetcode-cn.com/problems/house-robber-iii/

Test Ⅲ💠

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
print('house_rob_iii')
root = TreeNode(3, TreeNode(2,None,TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(house_rob_iii(root))
root = TreeNode(3,  TreeNode(4,TreeNode(1),TreeNode(3)), TreeNode(5, None, TreeNode(1)))
print(house_rob_iii(root))