Pythonのリーフ値からの最小コストツリー

正の整数の配列arrがあると仮定し、次のようなすべての二分木を検討します-

• 各ノードには0個または2個の子があります。
• arr配列の値は、ツリーを順番にトラバースする際の各リーフの値に対応します。
• 各非リーフノードの値は、それぞれその左サブツリーと右サブツリーの最大リーフ値の積に等しくなります。

考慮されるすべての可能な二分木の中で、各非リーフノードの値の可能な最小の合計を見つける必要があります。したがって、入力arrが[6,2,4]の場合、2つのツリーが存在する可能性があるため、出力は32になります-

これを解決するには、次の手順に従います-

• メモと呼ばれる地図を作成する
• メソッドdp（）を定義します。これは、パラメーターとしてiとjを取ります。これは次のように機能します-
• j <=iの場合、0を返します
• メモに（i、j）が含まれている場合は、メモを返します[（i、j）]
• res：=無限大
• 範囲iからj–1のkの場合
  • res：=resの最小値、dp（i、k）+ dp（k + 1、j）+（インデックスiからk + 1までのarrのサブ配列の最大値）* k+1からのarrのサブ配列の最大値to j + 1
• メモ[（i、j）]：=res
• メモを返す[（i、j）]
• メインメソッドは、このdp（）メソッドを次のように呼び出します-call dp（0、length of 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