舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
題目敘述 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框架。
Reference
[1] House Robber III - LeetCode
回到DP特訓班目錄 和 學習路徑
你可能也想看
