1130 葉值的最小代價生成樹（dfs、動态規劃）

1. 問題描述：

給你一個正整數數組 arr，考慮所有滿足以下條件的二叉樹：每個節點都有 0 個或是 2 個子節點。數組 arr 中的值與樹的中序周遊中每個葉節點的值一一對應。（知識回顧：如果一個節點有 0 個子節點，那麼該節點為葉節點）每個非葉節點的值等于其左子樹和右子樹中葉節點的最大值的乘積。在所有這樣的二叉樹中，傳回每個非葉節點的值的最小可能總和。這個和的值是一個 32 位整數。

示例：

輸入：arr = [6,2,4]

輸出：32

解釋：

有兩種可能的樹，第一種的非葉節點的總和為 36，第二種非葉節點的總和為 32。

   24           24

   / \            / \

  12 4       6  8

  / \               / \

 6 2             2 4

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values

提示：

• 2 <= arr.length <= 40

• 1 <= arr[i] <= 15

• 答案保證是一個 32 位帶符号整數，即小于 

  2^31

  。

2. 思路分析：

① 分析題目可以知道這道題題目有一個明顯的特點：需要嘗試所有的可能性才可以得到最終的結果，我們可以嘗試将清單劃分為兩棵子樹，分别求解出左右子樹非葉子節點的最小和和葉子節點的最大值，劃分的範圍不一樣那麼得到的結果也是不一樣的，是以可以使用dfs搜尋來解決，dfs搜尋的話可以嘗試所有的可能性并将最終的結果傳回，我們可以将清單劃分為兩個範圍，代表着左右子樹，分别遞歸左右子樹，求解出滿足題目要求的答案即可，對于每一個節點的左右子樹都是使用同樣的方法進行求解是以這也是能夠使用遞歸求解的一個條件

② 除了使用遞歸來解決，領扣的題解中使用的比較多的是動态規劃的思路來解決的，dp[i][j]的含義是從i到j範圍構成樹的最小的代價，從題目中可以分析得到狀态轉移方程：

具體可以使用三層循環來解決，第一層循環是左右子樹的長度範圍，第二層循環是左右子樹的起點，第三層循環表示這個範圍内劃分的左右子樹，結合上面的狀态轉移方程也比較好了解

3. 代碼如下：

dfs:（dfs需要添加上@lru_cache(maxsize=None)才可以通過）

import sys
from typing import List
from functools import lru_cache


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # dfs
        @lru_cache(maxsize=None)
        def dfs(l: int, r: int):
            # 葉子節點
            if l == r: return 0, arr[l]
            minsum, maxchild = sys.maxsize, sys.maxsize
            for i in range(l, r):
                # 左子樹的非葉子節點之和以及左子樹葉子節點的最大值
                lsum, lchild = dfs(l, i)
                # 右子樹的非葉子節點之和以及右子樹葉子節點的最大值
                rsum, rchild = dfs(i + 1, r)
                cur = lsum + rsum + lchild * rchild
                if cur < minsum:
                    minsum = cur
                    maxchild = max(lchild, rchild)
            return minsum, maxchild
        return dfs(0, len(arr) - 1)[0]
           

領扣中大佬寫的動态規劃代碼，題解：https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values/solution/dong-tai-gui-hua-dan-diao-zhan-python3-by-smoon1-2/

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        # 初始值設為最大
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]
        # 初始區間查詢最大值設為0
        maxval = [[0 for _ in range(n)] for _ in range(n)]
        # 求區間[i, j]中最大元素
        for i in range(n):
            for j in range(i, n):
                maxval[i][j] = max(arr[i:j + 1])
        # 葉子結點不參與計算
        for i in range(n):
            dp[i][i] = 0
        # 枚舉區間長度
        for l in range(1, n):
            # 枚舉區間起始點
            for s in range(n - l):
                # 枚舉劃分兩棵子樹
                for k in range(s, s + l):
                    dp[s][s + l] = min(dp[s][s + l], dp[s][k] + dp[k + 1][s + l] + maxval[s][k] * maxval[k + 1][s + l])
        return dp[0][n - 1]