पायथन में लीफ वैल्यू से न्यूनतम लागत का पेड़

मान लीजिए कि हमारे पास सकारात्मक पूर्णांकों की एक सरणी है, सभी बाइनरी पेड़ों पर विचार करें जैसे कि -

प्रत्येक नोड में 0 या 2 बच्चे होते हैं;
गिरफ्तारी सरणी के मान पेड़ के इन-ऑर्डर ट्रैवर्सल में प्रत्येक पत्ते के मूल्यों के अनुरूप होते हैं।
प्रत्येक गैर-पत्ती नोड का मान क्रमशः इसके बाएँ और दाएँ उपप्रकार में सबसे बड़े पत्ती मान के गुणनफल के बराबर होता है।

सभी संभावित द्विआधारी पेड़ों में से, हमें प्रत्येक गैर-पत्ती नोड के मूल्यों का सबसे छोटा संभव योग खोजना होगा। इसलिए यदि इनपुट गिरफ्तारी [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) + (इंडेक्स i से k + 1 तक एआर की अधिकतम सबएरे) * k + 1 से एआर की अधिकतम सबएरे से जे + 1
ज्ञापन[(i, j)] :=res
रिटर्न मेमो[(i, j)]
मुख्य विधि इस dp() विधि को - कॉल dp(0, गिरफ्तारी की लंबाई -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]