舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337

Digital Marketing Agency NTWRK on Unsplash

題目敘述 House Robber III

題目會給我們一個二元樹，
二元樹裡的每個節點分別代表每棟房屋的價值，也就是房屋內有的現金數量。

題目敘述給的情境是假想盜賊要偷東西，限制是上下相鄰樓層的兩棟房屋不能一起偷，只能選擇其中一棟，否則就會觸發警報器。

請問盜賊可以得手的最大金額是多少?

測試範例

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

下手的是上色的房屋，總共得到3+3+1=7單位的價值。​

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

下手的是上色的房屋，總共得到4+5=9​單位的價值。​

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].

節點總數量介於1~一萬。

• 0 <= Node.val <= 10^4

每隔節點的價值介於0~一萬之間。

觀察 樹型DP + 取/不取的模型

對於我自己這個節點來說，總共只有兩個選擇。

1.如果選了我自己，那麼下一層(的左右子節點)都不可以選。

得手的最大價值 = 自己的價值 + 下一層都不選的情況下的最大價值

2.如果不選自己，那麼下一層的節點就可以考慮。

得手的最大價值 = 自己不選得到0 + 下一層納入考慮的最大價值

從樹根開始往下搜索，什麼時候停下來?

遇到空節點的時候停下來。

空節點本身沒有價值，也沒有子樹，不管選或不選都是0，價值都是0。

演算法 樹型DP + 取/不取的模型

1.定義DP狀態

每個節點都有兩種可能，選 或者 不選。

定義 DP[ node ] = ( 選擇node得到的最大價值, 不選擇node得到的最大價值)

最後所求是什麼?

目標是整體的最大價值
= 從樹根開始考慮的最大價值
= Max( DP[ 樹根 ] ) = Max( DP[ root ] )

2.推導DP狀態轉移關係式

承接觀察點的思考

對於我自己這個節點node來說，總共只有兩個選擇。

1.如果選了我自己，那麼下一層(的左右子節點)都不可以選。

得手的最大價值
= 自己的價值 + 下一層都不選的情況下的最大價值
= 自己的價值 + 左子節點不選的情況下最大價值 + 右子節點不選的情況下最大價值

DP[ node ]

= node.val + DP[node.left][不選] + DP[node.right][不選]

= node.val + DP[node.left][1] + DP[node.right][1]

2.如果不選自己，那麼下一層的節點就可以考慮。

得手的最大價值
= 自己不選得到0 + 下一層納入考慮的最大價值
= 自己不選得到0 + 考慮左子節點的最大價值 + 考慮右子節點的最大價值

DP[ node ]

= 0 + Max( DP[node.left] ) + Max( DP[node.right] )

= Max( DP[node.left] ) + Max( DP[node.right] )

3.釐清DP初始條件

最小規模的問題是什麼?

從樹根開始往下搜索，什麼時候停下來?

空樹/空節點是最小規模的問題。

遇到空節點的時候停下來。

空節點本身沒有價值，也沒有子樹，不管選或不選都是0，價值都是0。

程式碼 樹型DP + 取/不取的模型

class Solution:
    def rob(self, root: TreeNode) -> int:
        
        TAKE, NOT_TO_TAKE = 0, 1
        
        def consider(node) -> (int, int):
            
            ## Base case
            if not node:
                # Empty node or empty tree
                # take, not to take
                return (0, 0)
            
            ## General cases
            left = consider(node.left)
            right = consider(node.right)
            
            #take current node                    
            take = node.val + left[NOT_TO_TAKE] + right[NOT_TO_TAKE]
            
            #discard current node
            discard = max(left) + max(right)
            
            return ( take, discard )
        
        # ---------------------------------
        
        return max( consider(node=root) )

複雜度分析

時間複雜度:O( n )

樹型DP，從樹根開始搜索整棵樹，每個節點恰好計算一次。

空間複雜度:O(n)

樹型DP，從樹根開始搜索整棵樹，每個節點恰好計算一次。

遞迴recursion call stack深度最深為O(n)

關鍵知識點 樹型DP + 取/不取的模型

取/不取 的模型 可以說貫穿了整個House Robbery系列題。

對於當下的房屋(節點)，只有兩種情況，取 或 不取。
取 或 不取 又會因為不可相鄰的限制條件影響接下來的選擇。

對於我自己這個節點來說，總共只有兩個選擇。

1.如果選了我自己，那麼下一層(的左右子節點)都不可以選。

得手的最大價值 = 自己的價值 + 下一層都不選的情況下的最大價值

2.如果不選自己，那麼下一層的節點就可以考慮。

得手的最大價值 = 自己不選得到0 + 下一層納入考慮的最大價值

記得一起復習相關的前兩題，鞏固 取 / 不取 這個模型的知識點和DP框架。

House Robbery I

House Robbery II

Reference

[1] House Robber III - LeetCode

回到DP特訓班目錄 和 學習路徑