今天來講講樹上的動態規劃問題吧～先來個一般的動態規劃暖身。

Exercise 40: Leetcode 337 - House Robber III

題目連結

https://leetcode.com/problems/house-robber-iii/

題目敘述

給你一棵二元樹。請選出樹上一些不相鄰的節點，使得加起來總數值最大。

解題思考

對以每一個點所形成的子樹，我們可以試圖計算「不選根節點」跟「選不選根節點都無妨」兩種狀態下能夠蒐集到的最大總和。此時我們便可以分情形討論，並得出遞迴關係。

• 不選根節點 = 左子樹的根選不選都無妨 + 右子樹的根選不選都無妨
• 選不選根都無妨 = max{ 不選根節點, 左子樹不選根節點 + 右子樹不選根節點 }

參考程式碼 (Python3)

class Solution:
    def solve(self, root: TreeNode) -> List[int]:
        if root == None:
            return [0, 0]
        l = self.solve(root.left)
        r = self.solve(root.right)
        return [l[1] + r[1], max(l[1]+r[1], l[0] + r[0] + root.val)]

    def rob(self, root: TreeNode) -> int:
        return self.solve(root)[1]

然後來講講今天真的想講的東西：在二元樹上，如果把左子樹 L 與右子樹 R 合併答案起來的時候，所需要花費的時間是 O((L*R)^k)。那麼簡單的估計會告訴我們 L ≤ N、R ≤ N、總共有 N 個節點，我們會得到一個 O(N^{2k+1}) 時間複雜度的演算法。但事實上，經過巧妙的分析，我們會發現，可以用數學歸納法證明，所花費的時間其實只有 O(N^{2k})。這是因為根據遞迴定義：T(L+R) = T(L) + T(R) + O((LR)^k)。這個解出來會得到 T(N) = O(N^{2k})。所以就現省了一個 N 呢！

Leetcode上面是不是沒有這種題目...

如果遇到多元樹怎麼辦呢？可以在此時使用 left-child right-sibling 的方法，先把這棵多元樹轉換成二元樹的形式。再搭配稍微修改動態規劃的狀態定義就可以囉！