198. 打家劫舍

• 思路
  • example
  • 二維DP
    • dp[i][j]: 房屋0,...,i; 并且第i個(gè)房屋狀態(tài)為j 的最高金額
    • j = 0: 不搶； j = 1: 搶 (帶狀態(tài)）
      • 狀態(tài)是i的單個(gè)狀態(tài)，不是0--i的整體狀態(tài)
    • 遞推公式：

有可能連續(xù)幾個(gè)房屋不搶
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) 取決于前一天的情況
dp[i][1] = dp[i-1][0] + nums[i]

• 復(fù)雜度. 時(shí)間：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, 不帶狀態(tài)
  • dp[i]: 房屋0,...,i; 最高金額

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
第i個(gè)不搶 vs 搶 (第i-1個(gè)必然不搶, 所以由兩天前的狀態(tài)轉(zhuǎn)移而來(lái))

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]

• 可以空間優(yōu)化

213. 打家劫舍 II

• 思路
  • example
  • 房屋圍成一圈, 轉(zhuǎn)化為兩個(gè)問(wèn)題I
    • 第0個(gè)不搶，最后一個(gè)可能搶也可能不搶。轉(zhuǎn)化為問(wèn)題1,...,n-1
    • 第0個(gè)搶，最后一個(gè)必然不搶。轉(zhuǎn)化為問(wèn)題0,...,n-2

注意指標(biāo)映射關(guān)系以及corner case （1個(gè)2個(gè)元素的情況)

• 復(fù)雜度. 時(shí)間：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 （在樹的結(jié)構(gòu)上使用DP）
    • 返回值包括 當(dāng)前根節(jié)點(diǎn)的兩種狀態(tài)
• 復(fù)雜度. 時(shí)間：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))

• 小結(jié)