Cây chi phí tối thiểu từ giá trị lá trong Python

Giả sử chúng ta có một dãy số nguyên dương, hãy xem xét tất cả các cây nhị phân sao cho -

• Mỗi nút có 0 hoặc 2 nút con;
• Các giá trị của mảng arr tương ứng với các giá trị của mỗi lá trong một đường truyền nhỏ hơn của cây.
• Giá trị của mỗi nút không phải là tích số của giá trị của lá lớn nhất trong cây con trái và phải của nó.

Trong số tất cả các cây nhị phân có thể được xem xét, chúng ta phải tìm tổng các giá trị nhỏ nhất có thể có của mỗi nút không phải là lá. Vì vậy, nếu arr đầu vào là [6,2,4], thì đầu ra sẽ là 32, vì có thể có hai cây -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bản đồ được gọi là bản ghi nhớ
• Xác định phương thức dp (), phương thức này sẽ nhận i và j làm tham số. Điều này sẽ hoạt động như sau -
• nếu j <=i, thì trả về 0
• if (i, j) trong bản ghi nhớ, sau đó trả về bản ghi nhớ [(i, j)]
• res:=infinity
• cho k trong phạm vi i đến j - 1
  • res:=min of res, dp (i, k) + dp (k + 1, j) + (max of arr of arr from index i to k + 1) * max of subarray of arr from k + 1 đến j + 1
• memo [(i, j)]:=res
• trả lại thư báo [(i, j)]
• Phương thức chính sẽ gọi phương thức dp () này là - gọi dp (0, độ dài của arr - 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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)

Đầu vào

[6,2,4]

Đầu ra

32