您现在的位置是:首页 >学无止境 >算法记录 | 48 动态规划网站首页学无止境

算法记录 | 48 动态规划

是菜鸡小小陈啊 2023-07-08 16:00:02
简介算法记录 | 48 动态规划

198.打家劫舍

思路:

1.确定dp数组(dp table)以及下标的含义:dp[i]:前 i 间房屋所能偷窃到的最高金额。

2.确定递推公式:dp[i] = max(dp[i - 2] + nums[i-1], dp[i - 1])

i间房屋的最后一个房子是nums[i−1]。

如果房屋数大于等于 2 间,则偷窃第 i−1 间房屋的时候,就有两种状态:

  1. 偷窃第 i−1 间房屋,那么第 i-2 间房屋就不能偷窃了,偷窃的最高金额为:前 i−2 间房屋的最高总金额 + 第 i−1 间房屋的金额,即 dp[i]=dp[i−2]+nums[i-1];

  2. 不偷窃第 i−1 间房屋,那么第 i−2 间房屋可以偷窃,偷窃的最高金额为:前 i−1 间房屋的最高总金额,即 dp[i]=dp[i−1]。

  3. 初始条件:

    • 前 0 间房屋所能偷窃到的最高金额为 0,即 dp[0]=0。

    • 前 1 间房屋所能偷窃到的最高金额为 nums[0],即:dp[1]=nums[0]。

  4. 确定遍历顺序:dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历

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

        return dp[size]

213.打家劫舍II

思路:

这道题可以看做是「198. 打家劫舍」的升级版。

如果房屋数大于等于 3 间,偷窃了第 1 间房屋,则不能偷窃最后一间房屋。同样偷窃了最后一间房屋则不能偷窃第 1 间房屋。

假设总共房屋数量为size,这种情况可以转换为分别求解 [0,size−2] 和 [1,size−1] 范围下首尾不相连的房屋所能偷窃的最高金额,然后再取这两种情况下的最大值。而求解 [0,size−2] 和 [1,size−1] 范围下首尾不相连的房屋所能偷窃的最高金额问题就跟「198. 打家劫舍」所求问题一致了。

class Solution:
    def helper(self, nums):
        size = len(nums)
        if size == 0:
            return 0
 
        dp = [0 for _ in range(size + 1)]
        dp[0] = 0
        dp[1] = nums[0]
        
        for i in range(2, size + 1):
            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])

        return dp[size]

    def rob(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 1:
            return nums[0]
        
        ans1 = self.helper(nums[:size - 1])
        ans2 = self.helper(nums[1:])
        return max(ans1, ans2)

337.打家劫舍III

思路:

树形动态规划问题。

对于当前节点 cur,不能选择子节点,也不能选择父节点。所以对于一棵子树来说,有两种情况:

  • 选择了根节点
  • 没有选择根节点

1.选择根节点

如果选择了根节点,则不能再选择左右儿子节点,这种情况下的最大值为:当前节点 + 左子树不选择根节点 + 右子树不选择根节点。

不选择根节点

2.如果不选择根节点,则可以选择左右儿子节点,共四种可能:

  • 左子树选择根节点 + 右子树选择根节点
  • 左子树选择根节点 + 右子树不选根节点
  • 左子树不选根节点 + 右子树选择根节点
  • 左子树不选根节点 + 右子树不选根节点

选择其中最大值。

# 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)
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。