代码随想录算法训练营第四十八天| LeetCode198. 打家劫舍、LeetCode213. 打家劫舍 II、LeetCode337. 打家劫舍 III

一、LeetCode198. 打家劫舍

        1：题目描述（198. 打家劫舍）

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

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

        2：解题思路

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 1：确定dp数组的定义：dp[j]表示下标j（包括j）以内的房屋，最多可以偷窃的金额为dp[j]
        # 2：确定递推公式，分两种，j号房偷和不偷
        # j号房偷，dp[j] = dp[j-2]+nums[j]
        # j号房不偷，dp[j] = dp[j-1]
        # 要取偷窃的最大金额，所以dp[j]=max(dp[j-2]+nums[j], dp[j-1])
        # 3：初始化，根据递推公式，后面的需要由j-2，j-1推出，所以dp[0],dp[1]需要进行初始化
        # dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])
        # 4：遍历顺序，因为需要由dp[j-1],dp[j-2]推出，所以从前向后遍历
        if len(nums) == 0:
            return 0          # nums为空，直接返回0
        if len(nums) == 1:
            return nums[0]    # nums长度为1，只能偷一间，返回nums[0]
        dp = [0] * len(nums)      # 先将dp数组都初始化为0，长度就是nums的长度
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for j in range(2, len(nums)):
            dp[j] = max(dp[j-2] + nums[j], dp[j-1])
        return max(dp)

二、LeetCode213. 打家劫舍 II

        1：题目描述（213. 打家劫舍 II）

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

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

        2：解题思路

        本题对于198. 打家劫舍来说，多了一个限制条件，就是最后一个房间是与第1个房间相连的，所以就可以分为：偷第一间房，就不能偷最后一间；偷最后一间房，就不能偷第一间房

        偷第一间房，就不能偷最后一间：可以将nums切割成不含最后一个元素的nums，进行求偷窃的最大金额

        偷最后一间房，就不能偷第一间房：就将nums切割成不含首个元素的nums，进行求偷窃的最大金额

        最后取两种情况下，偷窃金额最大的值作为返回结果

        其中在计算两种情况下的偷窃最大金额时，初始化的时候，只初始化dp[0]，不初始化dp[1]？

        dp[1] = max(nums[0], nums[1])  

        为什么不能初始化dp[1],因为nums是去掉了首元素或尾元素的，如果原始的nums长度为2，去掉首元素或尾元素后，传入robRange()函数的nums长度为1，只有nums[0]，此时使用dp[1] = max(nums[0], nums[1])会报错，因为找不到nums[1]

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 分两种情况
        # 1：不偷第一间房
        # 2：不偷最后一间
        if len(nums) == 1:
            return nums[0]
        nums1 = self.robRange(nums[:len(nums)-1])       # 不偷最后一间房，得到的偷窃最大金额
        nums2 = self.robRange(nums[1:])                 # 不偷第一间房，得到的偷窃最大金额
        return max(nums1, nums2)           # 取两种情况中的最大金额
 
    def robRange(self, nums):
        # 1：确定dp数组的定义：dp[j]表示下标j（包括j）以内的房屋，最多可以偷窃的金额为dp[j]
        # 2：确定递推公式，分两种，j号房偷和不偷
        # j号房偷，dp[j] = dp[j-2]+nums[j]
        # j号房不偷，dp[j] = dp[j-1]
        # 要取偷窃的最大金额，所以dp[j]=max(dp[j-2]+nums[j], dp[j-1])
        # 3：初始化，根据递推公式，后面的需要由j-2，j-1推出，所以dp[0],dp[1]需要进行初始化
        # dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1])
        # 4：遍历顺序，因为需要由dp[j-1],dp[j-2]推出，所以从前向后遍历
        dp = [0] * len(nums)
        dp[0] = nums[0]
        # dp[1] = max(nums[0], nums[1])   
        # 为什么不能初始化dp[1],因为nums是去掉了首元素或尾元素的，如果原始的nums长度为2，去掉首元素或尾元素后，传入robRange()函数的nums长度为1，只有nums[0]，此时使用dp[1] = max(nums[0], nums[1])会报错，因为找不到nums[1]
        for j in range(1, len(nums)):
            if j == 1:
                # j==1，偷1号房，取nums[j],不偷1号房，取dp[0],取两者中的最大值
                dp[j] = max(dp[0], nums[j])      
            else:
                dp[j] = max(dp[j-2]+nums[j], dp[j-1])
        return dp[-1]

三、LeetCode337. 打家劫舍 III

        1：题目描述（337. 打家劫舍 III）

        小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

        除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

        给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

        2：解题思路

        需要使用后序遍历进行遍历二叉树，关键是要讨论当前节点抢还是不抢。如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子

        1：确定递归函数的参数和返回值

        这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

        递归函数的返回值就是dp数组

        所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

        2：确定终止条件

        在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

if node == None:
    return(0, 0)

        这也相当于dp数组的初始化

        3：确定遍历顺序

        首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。

        通过递归左节点，得到左节点偷与不偷的金钱。

        通过递归右节点，得到右节点偷与不偷的金钱。

# 向左递归
left = self.traversal(node.left) 
# 向右递归      
right = self.traversal(node.right) 

        4：确定单层递归的逻辑

        如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; 

        如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

        最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

# 向左递归
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]

        最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。

代码如下：

# 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 node == None:
            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)