Day 48 DP：198|213|337. 打家劫舍 I II III

198. 打家劫舍

• 思路
  • example
  • 二维DP
    • dp[i][j]: 房屋0,...,i; 并且第i个房屋状态为j 的最高金额
    • j = 0: 不抢； j = 1: 抢 (带状态）
      • 状态是i的单个状态，不是0--i的整体状态
    • 递推公式：

有可能连续几个房屋不抢
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) 取决于前一天的情况
dp[i][1] = dp[i-1][0] + nums[i]

• 复杂度. 时间：O(n), 空间: O(n)

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

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

• 一维DP, 不带状态
  • dp[i]: 房屋0,...,i; 最高金额

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
第i个不抢 vs 抢 (第i-1个必然不抢, 所以由两天前的状态转移而来)

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

• 可以空间优化

213. 打家劫舍 II

• 思路
  • example
  • 房屋围成一圈, 转化为两个问题I
    • 第0个不抢，最后一个可能抢也可能不抢。转化为问题1,...,n-1
    • 第0个抢，最后一个必然不抢。转化为问题0,...,n-2

注意指标映射关系以及corner case （1个2个元素的情况)

• 复杂度. 时间：O(n), 空间: O(n)

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

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

337. 打家劫舍 III

• 思路
  • example
  • 递归，后序遍历，自下而上
  • 树形DP （在树的结构上使用DP）
    • 返回值包括 当前根节点的两种状态
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            if root == None:
                return 0, 0 
            left0, left1 = traversal(root.left)
            right0, right1 = traversal(root.right) 
            return max(left0, left1)+max(right0, right1), left0+right0+root.val 
        return max(traversal(root))

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            if root == None:
                return 0, 0
            left0, left1 = traversal(root.left) 
            right0, right1 = traversal(root.right) 
            return max(left0, left1)+max(right0, right1), left0+right0+root.val 
        return max(traversal(root)) 

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def traverse(root):
            if root == None:
                return 0, 0 
            left_0, left_1 = traverse(root.left) 
            right_0, right_1 = traverse(root.right) 
            return max(left_0, left_1)+max(right_0, right_1), left_0 + right_0 + root.val
        return max(traverse(root))

• 小结