代码随想录算法训练营Day48 (day47休息) | 动态规划(9/17) LeetCode 198.打家劫舍 213.打家劫舍II 337.打家劫舍III

来到了新的一块内容：打家劫舍问题。

第一题

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

直觉告诉我，可能会涉及到一些贪心问题，为了保证利益最大，可能要找钱最多的地方优先动手。而当前房屋偷与不偷取决于，前一个房屋和前两个房屋是否被偷了。

仍然可以利用动态规划五部曲来解决。

1. 确定dp数组（dp table）以及下标的含义
   1. dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2. 确定递推公式
   1. 决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
   2. 如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3. dp数组如何初始化
   1. 从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
   2. 从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
4. 确定遍历顺序

   1. dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

5. 举例推导dp数组

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:  
            return 0
        if len(nums) == 1:  
            return nums[0]
 
        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 - 2] + nums[i], dp[i - 1])
 
        return dp[-1] 

第二题

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

和前一题比较，这道题变成环状了，需要考虑下面三个因素：

对于一个数组，成环的话主要有如下三种情况：

• 情况一：考虑不包含首尾元素
• 情况二：考虑包含首元素，不包含尾元素
• 情况三：考虑包含尾元素，不包含首元素

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:  # 如果没有房屋，返回0
            return 0
 
        if len(nums) == 1:  # 如果只有一个房屋，返回该房屋的金额
            return nums[0]
 
        # 情况二：不抢劫第一个房屋
        prev_max = 0  # 上一个房屋的最大金额
        curr_max = 0  # 当前房屋的最大金额
        for num in nums[1:]:
            temp = curr_max  # 临时变量保存当前房屋的最大金额
            curr_max = max(prev_max + num, curr_max)  # 更新当前房屋的最大金额
            prev_max = temp  # 更新上一个房屋的最大金额
        result1 = curr_max
 
        # 情况三：不抢劫最后一个房屋
        prev_max = 0  # 上一个房屋的最大金额
        curr_max = 0  # 当前房屋的最大金额
        for num in nums[:-1]:
            temp = curr_max  # 临时变量保存当前房屋的最大金额
            curr_max = max(prev_max + num, curr_max)  # 更新当前房屋的最大金额
            prev_max = temp  # 更新上一个房屋的最大金额
        result2 = curr_max
 
        return max(result1, result2)

第三题

 337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

class Solution:
    def rob(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left is None and root.right  is None:
            return root.val
        # 偷父节点
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # 不偷父节点
        val2 = self.rob(root.left) + self.rob(root.right)
        return max(val1, val2)