leetcode - 动态规划 - Part2

198. 打家劫舍

题目描述

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

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

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

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

提示： 
0 <= nums.length <= 100 
0 <= nums[i] <= 400 

Related Topics 动态规划

分析求解
因为不能同时偷窃相邻的两间房屋，当我们考察第 $i$ 间房屋的时候，能偷到的总体金额和前面 $i-2$ 间房屋能偷取的金额有关，因其状态转移能从 $0,1,\cdots,i-2$ 任何一个转移而来。又我们需要求得最大金额，那么可以将状态定义为 $dp[i]$ 表示前 $i$ 间房屋能偷到的最大金额，则 $0,1,\cdots,i-2$ 中的最大值为 $i-2$ 的状态。

对于房间 $i$ ，有两种选择：偷或者不偷。

选择偷，则 $dp[i] = dp[i-2] + nums[i]$
选择不偷，则 $dp[i] = dp[i-1]$
所以我们的状态转移方程为
$dp[i] = max(dp[i-2] + nums[i], dp[i-1])$
相应的实现代码如下：

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] 表示偷窃到 i 号房屋时的最高金额
        n = len(nums)
        if n == 0:
            return 0
        dp = [0] * n
        for i in range(n):
            if i == 0:
                dp[i] = nums[i]
            elif i == 1:
                dp[i] = max(nums[0], nums[1])
            else:
                dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[n-1]

时间和空间复杂度均为 $O(n)$ 。

继续尝试对空间复杂度进行优化。由于 $dp[i]$ 只和 $dp[i-1]$ 和 $dp[i-2]$ 有关，我们可以定义两个变量来记录不同状态，这样能将空间复杂度降低至 $O(1)$ 。

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

213. 打家劫舍 II

题目描述

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

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

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

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

Related Topics 动态规划

分析求解
此题和上一题非常相似，不同点在于房屋是环状连接的，这也意味着第 $0$ 号房屋和第 $n-1$ 号房屋不能同时被偷。所以我们可以针对第 $0$ 号房屋是否选择被偷分别讨论求解。因为其他和上一题一致，所以就不贴代码了。

337. 打家劫舍 III

题目描述

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

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

示例 2: 
输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
 
Related Topics 树 深度优先搜索

分析求解
对于某个节点 root，我们有两种选择偷与不偷。假如我们选择偷，则其左右子节点就不能选择偷；如果我们选择不偷，则左右子节点我们可以选择偷也可以选择不偷。最后的结果就是取这两种情况下的最大值。

我们要求能够盗取的最大金额。根据上面的思路，我们细化一下：

假如我们选择偷节点 root，此时能盗取的最大金额为 root 节点的金额加上其左右子树上盗取的金额。由于我们选择了 root，所以其左右子节点不能选择，但是其孙子节点(左右子节点的子节点) 可以自由选择，即递归其孙子节点(因为它们面临的情况和节点 root 是一致的)。
假如我们选择不偷节点 root，此时能盗取的最大金额为其左右子树上盗取的金额，即递归其左右子节点(此时它们面临的情况和节点 root 是一致的)。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        # 选择偷节点root
        selected = root.val
        if root.left is not None:
            selected += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right is not None:
            selected += self.rob(root.right.left) + self.rob(root.right.right)
        # 选择不偷节点root
        not_selected = self.rob(root.left) + self.rob(root.right)
        return max(selected, not_selected)

这里的递归有很多重复计算，所以可以采用记忆化方法进行优化。

class Solution:
    def __init__(self):
        self.memory = {}

    def rob(self, root: TreeNode) -> int:
        if root in self.memory:
            return self.memory[root]
        if not root:
            return 0
        # 选择偷节点root
        selected = root.val
        if root.left is not None:
            selected += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right is not None:
            selected += self.rob(root.right.left) + self.rob(root.right.right)
        # 选择不偷节点root
        not_selected = self.rob(root.left) + self.rob(root.right)
        self.memory[root] = max(selected, not_selected)
        return self.memory[root]

既然有记忆化解法，那是否有动态规划的解法呢？
对于每个节点 root，它对应着两个状态：被选择或者未被选择。我们进行状态转移的时候，需要同时考虑到这两个状态，因此都需要记录。我们可以这样设计状态 dp[root] = [not_selected, selected]。 $dp$ 是一个哈希表，其键为节点，值为一个数组，表示该节点是否被选择的两种情况下盗取的最大金额。

class Solution:
    def rob(self, root: TreeNode) -> int:

        def dfs(root):
            if not root:
                return [0, 0]
            left = dfs(root.left)
            right = dfs(root.right)
            selected = root.val + left[0] + right[0]
            not_selected = max(left[0], left[1]) + max(right[0], right[1])
            # 记录状态
            dp[root] = [not_selected, selected]
            # 返回状态，供父节点参考
            return [not_selected, selected]
        
        dp = {}
        res = dfs(root)
        return max(res)

仔细分析以上代码，当前节点 root 的状态受到其左右子树的状态影响，而与其他节点无关，因此我们考虑对空间复杂度进行优化。利用两个变量记录左右子树的状态，返回供父节点调用即可。

class Solution:
    def rob(self, root: TreeNode) -> int:

        def dfs(root):
            if not root:
                return [0, 0]
            left = dfs(root.left)
            right = dfs(root.right)
            selected = root.val + left[0] + right[0]
            not_selected = max(left[0], left[1]) + max(right[0], right[1])
            # 返回状态，供父节点参考
            return [not_selected, selected]
        
        res = dfs(root)
        return max(res)