ต้นไม้ต้นทุนขั้นต่ำจากค่าลีฟใน Python

สมมติว่าเรามีอาร์เรย์ arr ของจำนวนเต็มบวก พิจารณาไบนารีทรีทั้งหมดเช่นนั้น −

• แต่ละโหนดมี 0 หรือ 2 ลูก
• ค่าของอาร์เรย์ arr สอดคล้องกับค่าของแต่ละลีฟในการข้ามผ่านของต้นไม้
• ค่าของโหนดที่ไม่ใช่ใบไม้แต่ละโหนดจะเท่ากับผลคูณของค่าลีฟที่ใหญ่ที่สุดในทรีย่อยด้านซ้ายและด้านขวาตามลำดับ

ในบรรดาต้นไม้ไบนารีที่เป็นไปได้ทั้งหมดที่เราพิจารณา เราต้องหาผลรวมที่น้อยที่สุดของค่าของแต่ละโหนดที่ไม่ใช่ใบไม้ ดังนั้นหากอินพุต arr เป็น [6,2,4] เอาต์พุตจะเป็น 32 เนื่องจากอาจมีต้นไม้สองต้น -

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างแผนที่ชื่อบันทึก
• กำหนดวิธีการ dp() ซึ่งจะใช้ i และ j เป็นพารามิเตอร์ สิ่งนี้จะทำงานดังนี้ −
• ถ้า j <=i ให้คืนค่า 0
• ถ้า (i, j) ในบันทึกช่วยจำ ให้ส่งคืนบันทึก[(i, j)]
• res :=อินฟินิตี้
• สำหรับ k ในช่วง i ถึง j – 1
  • res :=นาทีของ res, dp(i, k) + dp(k + 1, j) + (สูงสุดของ subarray ของ arr จากดัชนี i ถึง k + 1) * สูงสุดของ subarray ของ arr จาก k + 1 ถึง j + 1
• บันทึก[(i, j)] :=res
• return 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