代码随想录 动态规划Ⅸ

198. 打家劫舍

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

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

思路：状态转换机经典题目 dp[i][0]表示第i个房间不偷的最高金额，dp[i]表示第i个房屋偷的最高金额，状态转移方程为 dp[i][0] =max(dp[i-1][1] dp[i-1][0]), dp[i][1] = dp[i-1][0] + nums[i]. 最后返回max(dp[-1][0], dp[-1][1].初始化：dp[0][0] = 0, dp[0][0][1]=nums[0]

python:

二维dp

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp= [[0,0] for _ in range(len(nums))]
 
        dp[0][0] = 0
        dp[0][1] = nums[0]
 
        for i in range(1, len(dp)):
            dp[i][0] = max(dp[i-1][1], dp[i-1][0])
            dp[i][1] = dp[i-1][0] + nums[i]
 
        return max(dp[-1][0], dp[-1][1])

一维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的第一个元素设置为第一个房屋的金额
        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]  # 返回最后一个房屋中可抢劫的最大金额

 213. 打家劫舍 II

思路：与打家劫舍Ⅰ的区别在于这个成了一个环状，可以想办法把题目转换成打家劫舍Ⅰ。一个思路是分情况考虑，一个是考虑第一个房子，一个是考虑最后一个房子。然后从两种情况的最大值中选择最大的那个。

python：二维dp

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return max(nums)
 
        # 不抢劫第一个房屋
        result1 = self.robRange(nums[:-1])
 
        # 不抢劫最后一个房屋
        result2 = self.robRange(nums[1:])
 
        return max(result1, result2)
 
    # 打家劫舍Ⅰ
    def robRange(self, nums):
        dp = [[0, 0] for _ in range(len(nums))]
        dp[0][1] = nums[0]
 
        for i in range(1, len(nums)):
            dp[i][0] = max(dp[i - 1])
            dp[i][1] = dp[i - 1][0] + nums[i]
 
        return max(dp[-1])

python：双指针（一维dp）

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. 打家劫舍 III

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

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

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

思路：递归加dp

因为是树，所以需要遍历。父亲结点是否可以考虑偷，考不考虑时的价值如何，需要根据左右孩子的状况而定，因此需要后序遍历，利用左右孩子的状态来决定父亲节点的状态，最后根据根节点的状态来得到最高金额。因为偷或不偷，那么设置每一个节点的dp数组为dp[0]dp[1], 转移方程为：dp[0] 的数值为左右孩子各自max(dp[0], dp[1])的最大值的和，dp[1]为左右孩子dp[0]的和加上节点的金额。

python:

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        final_dp = self.backtrack(root)
        return max(final_dp[0], final_dp[1])
        
 
    
    def backtrack(self, node):
        # stop condition
        if not node:
            return [0,0]
 
        dp = [0,0]
        
        
        left_dp = self.backtrack(node.left)
        right_dp = self.backtrack(node.right)
 
        dp[0] = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])
        dp[1] = left_dp[0] + right_dp[0] + node.val
 
        return dp