Python实现最小成本叶值树

假设我们有一个正整数数组arr，考虑所有满足以下条件的二叉树：

  • 每个节点要么有0个子节点，要么有2个子节点；
  • 数组arr的值对应于树的中序遍历中每个叶子的值。
  • 每个非叶子节点的值等于其左右子树中最大叶节点值的乘积。

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

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

  • 创建一个名为memo的映射
  • 定义一个名为dp()的方法，它将i和j作为参数。它的工作原理如下：
  • 如果j <= i，则返回0
  • 如果(i, j)在memo中，则返回memo[(i, j)]
  • res := 无穷大
  • 对于k从i到j – 1的范围
    • res := res，dp(i, k) + dp(k + 1, j) + (arr从索引i到k + 1子数组的最大值) * (arr从k + 1到j + 1子数组的最大值)的最小值
  • 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

更新于：2020年3月5日

382 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告