Python의 리프 값에서 최소 비용 트리

<시간/>

양의 정수 배열 arr이 있다고 가정하고 모든 이진 트리를 다음과 같이 고려합니다. -

각 노드에는 0 또는 2개의 자식이 있습니다.
arr 배열의 값은 트리의 inorder traversal에서 각 잎의 값에 해당합니다.
잎이 아닌 각 노드의 값은 각각 왼쪽 및 오른쪽 하위 트리에서 가장 큰 잎 값의 곱과 같습니다.

고려되는 모든 가능한 이진 트리 중에서 잎이 아닌 각 노드 값의 가능한 가장 작은 합을 찾아야 합니다. 따라서 입력 arr이 [6,2,4]이면 두 개의 트리가 있을 수 있으므로 출력은 32가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

메모라는 지도 만들기
dp() 메서드를 정의하면 i와 j가 매개변수로 사용됩니다. 이것은 다음과 같이 작동합니다 -
j <=i이면 0을 반환
메모에 (i, j)가 있으면 메모를 반환[(i, j)]
res :=무한대
i ~ j 범위의 k에 대해 – 1
- res :=res의 최소값, dp(i, k) + dp(k + 1, j) + (인덱스 i에서 k + 1까지의 arr 부분배열의 최대값) * k + 1에서 arr의 부분배열 최대값 j + 1로
메모[(i, j)] :=res
반품 메모[(i,j)]
메인 메소드는 이 dp() 메소드를 다음과 같이 호출합니다. 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]