leetcode - 動態(tài)規(guī)劃 - Part2

198. 打家劫舍

題目描述

你是一個專業(yè)的小偷蔬蕊，計劃偷竊沿街的房屋岸夯。每間房內(nèi)都藏有一定的現(xiàn)金猜扮，
影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)监婶，
如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警煮盼。 

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組僵控，計算你不觸動警報裝置的情況下 鱼冀，
一夜之內(nèi)能夠偷竊到的最高金額。 

示例 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 動態(tài)規(guī)劃

分析求解
因為不能同時偷竊相鄰的兩間房屋，當我們考察第 $i$ 間房屋的時候毙驯，能偷到的總體金額和前面 $i-2$ 間房屋能偷取的金額有關(guān)灾测，因其狀態(tài)轉(zhuǎn)移能從 $0,1,\cdots,i-2$ 任何一個轉(zhuǎn)移而來媳搪。又我們需要求得最大金額，那么可以將狀態(tài)定義為 $dp[i]$ 表示前 $i$ 間房屋能偷到的最大金額序愚，則 $0,1,\cdots,i-2$ 中的最大值為 $i-2$ 的狀態(tài)展运。

對于房間 $i$ 精刷，有兩種選擇：偷或者不偷怒允。

選擇偷，則 $dp[i] = dp[i-2] + nums[i]$
選擇不偷勘畔，則 $dp[i] = dp[i-1]$
所以我們的狀態(tài)轉(zhuǎn)移方程為
$dp[i] = max(dp[i-2] + nums[i], dp[i-1])$
相應(yīng)的實現(xiàn)代碼如下：

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]

時間和空間復(fù)雜度均為 $O(n)$ 炫七。

繼續(xù)嘗試對空間復(fù)雜度進行優(yōu)化万哪。由于 $dp[i]$ 只和 $dp[i-1]$ 和 $dp[i-2]$ 有關(guān)抡秆，我們可以定義兩個變量來記錄不同狀態(tài)儒士，這樣能將空間復(fù)雜度降低至 $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

題目描述

你是一個專業(yè)的小偷诅福，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金剩檀。
這個地方所有的房屋都圍成一圈旺芽，這意味著第一個房屋和最后一個房屋是緊挨著的采章。
同時壶辜，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入抵怎，
系統(tǒng)會自動報警反惕。 

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組演侯，計算你在不觸動警報裝置的情況下，
能夠偷竊到的最高金額悬赏。 

示例 1: 
輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 號房屋（金額 = 2）娄徊，然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的寄锐。

示例 2: 
輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）中鼠。
偷竊到的最高金額 = 1 + 3 = 4 沿癞。 

Related Topics 動態(tài)規(guī)劃

分析求解
此題和上一題非常相似椎扬，不同點在于房屋是環(huán)狀連接的具温，這也意味著第 $0$ 號房屋和第 $n-1$ 號房屋不能同時被偷铣猩。所以我們可以針對第 $0$ 號房屋是否選擇被偷分別討論求解达皿。因為其他和上一題一致贿肩，所以就不貼代碼了能曾。

337. 打家劫舍 III

題目描述

在上次打劫完一條街道之后和一圈房屋后告私，小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)屿良。
這個地區(qū)只有一個入口，我們稱之為“根”餐茵。 除了“根”之外钟病，每棟房子有且只有一
個“父“房子與之相連刚梭。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列
類似于一棵二叉樹”屹徘。 如果兩個直接相連的房子在同一天晚上被打劫衅金，房屋將自動報警。 
計算在不觸動警報的情況下鉴吹，小偷一晚能夠盜取的最高金額惩琉。 

示例 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 樹 深度優(yōu)先搜索

分析求解
對于某個節(jié)點 root，我們有兩種選擇偷與不偷技扼。假如我們選擇偷，則其左右子節(jié)點就不能選擇偷剿吻；如果我們選擇不偷丽旅，則左右子節(jié)點我們可以選擇偷也可以選擇不偷造垛。最后的結(jié)果就是取這兩種情況下的最大值。

我們要求能夠盜取的最大金額五辽。根據(jù)上面的思路杆逗，我們細化一下：

假如我們選擇偷節(jié)點 root罪郊，此時能盜取的最大金額為 root 節(jié)點的金額加上其左右子樹上盜取的金額尚洽。由于我們選擇了 root，所以其左右子節(jié)點不能選擇癣疟，但是其孫子節(jié)點(左右子節(jié)點的子節(jié)點) 可以自由選擇潮酒，即遞歸其孫子節(jié)點(因為它們面臨的情況和節(jié)點 root 是一致的)急黎。
假如我們選擇不偷節(jié)點 root，此時能盜取的最大金額為其左右子樹上盜取的金額勃教，即遞歸其左右子節(jié)點(此時它們面臨的情況和節(jié)點 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
        # 選擇偷節(jié)點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)
        # 選擇不偷節(jié)點root
        not_selected = self.rob(root.left) + self.rob(root.right)
        return max(selected, not_selected)

這里的遞歸有很多重復(fù)計算心软，所以可以采用記憶化方法進行優(yōu)化著蛙。

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
        # 選擇偷節(jié)點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)
        # 選擇不偷節(jié)點root
        not_selected = self.rob(root.left) + self.rob(root.right)
        self.memory[root] = max(selected, not_selected)
        return self.memory[root]

既然有記憶化解法踏堡，那是否有動態(tài)規(guī)劃的解法呢顷蟆？
對于每個節(jié)點 root腐魂，它對應(yīng)著兩個狀態(tài)：被選擇或者未被選擇。我們進行狀態(tài)轉(zhuǎn)移的時候削樊，需要同時考慮到這兩個狀態(tài)兔毒，因此都需要記錄。我們可以這樣設(shè)計狀態(tài) dp[root] = [not_selected, selected]迅脐。 $dp$ 是一個哈希表谴蔑，其鍵為節(jié)點，值為一個數(shù)組隐锭，表示該節(jié)點是否被選擇的兩種情況下盜取的最大金額成榜。

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])
            # 記錄狀態(tài)
            dp[root] = [not_selected, selected]
            # 返回狀態(tài)蹦玫，供父節(jié)點參考
            return [not_selected, selected]
        
        dp = {}
        res = dfs(root)
        return max(res)

仔細分析以上代碼，當前節(jié)點 root 的狀態(tài)受到其左右子樹的狀態(tài)影響挣输，而與其他節(jié)點無關(guān)撩嚼，因此我們考慮對空間復(fù)雜度進行優(yōu)化。利用兩個變量記錄左右子樹的狀態(tài)完丽，返回供父節(jié)點調(diào)用即可。

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])
            # 返回狀態(tài)蜻底，供父節(jié)點參考
            return [not_selected, selected]
        
        res = dfs(root)
        return max(res)