Python 中从叶子值构建最小成本树

pythonserver side programmingprogramming更新于 2025/8/25 16:44:17

假设我们有一个正整数数组 arr,考虑所有满足 − 的二叉树

  • 每个节点有 0 个或 2 个子节点;
  • arr 数组的值对应于树中序遍历中每个叶子的值。
  • 每个非叶子节点的值分别等于其左子树和右子树中最大叶子值的乘积。

在考虑的所有可能的二叉树中,我们必须找到每个非叶子节点值的最小可能总和。因此,如果输入 arr 是 [6,2,4],则输出将为 32,因为可能有两棵树 −

为了解决这个问题,我们将遵循以下步骤 −

  • 制作一个名为 memo 的地图
  • 定义一个方法 dp(),它将以 i 和 j 作为参数。这将按如下方式工作 −
  • 如果 j <= i,则返回 0
  • 如果 (i, j) 在备忘录中,则返回 memo[(i, j)]
  • res := infinity
  • 对于范围从 i 到 j – 1 的 k
    • res := min of res,dp(i, k) + dp(k + 1, j) + (从索引 i 到 k + 1 的 arr 子数组的最大值) * 从 k + 1 到 j + 1 的 arr 子数组的最大值
  • memo[(i, j)] := res
  • 返回 memo[(i, j)]
  • 主方法将调用此 dp() 方法作为 −调用 dp(0, arr 的长度 - 1)

让我们看看下面的实现以便更好地理解 −

示例

class Solution(object):
   def mctFromLeafValues(self, arr):
      """
      :type arr: List[int]
      :rtype: int
      """
      self. memo = {}
      def dp(i,j):
         if j<=i:
            return 0
         if (i,j) in self.memo:
            return self.memo[(i,j)]
         res = float('inf')
         for k in range(i,j):
            res = min(res,dp(i,k) + dp(k+1,j) + (max(arr[i:k+1])*max(arr[k+1:j+1])))
         self.memo[(i,j)]=res
         return self.memo[(i,j)]
      return dp(0,len(arr)-1)

输入

[6,2,4]

输出

32

相关文章


有用资源