पायथन में लीफ वैल्यूज से न्यूनतम लागत ट्री

मान लीजिए हमारे पास पॉजिटिव इंटीजर्स का एक ऐरे arr है, उन सभी बाइनरी ट्री पर विचार करें जैसे कि -

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

विचार किए गए सभी संभावित बाइनरी ट्री में से, हमें प्रत्येक नॉन-लीफ नोड के मानों के योग का सबसे छोटा संभव योग ढूंढना है। इसलिए यदि इनपुट arr [6,2,4] है, तो आउटपुट 32 होगा, क्योंकि संभावित दो ट्री हो सकते हैं -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

memo नामक एक मैप बनाएं
dp() नामक एक मेथड परिभाषित करें, यह पैरामीटर के रूप में i और j लेगा। यह निम्नानुसार काम करेगा -
यदि j <= i, तो 0 लौटाएं
यदि (i, j) memo में है, तो memo[(i, j)] लौटाएं
res := अनंत
k को i से j - 1 तक रेंज में
- res := res का न्यूनतम, dp(i, k) + dp(k + 1, j) + (arr के सबऐरे का अधिकतम इंडेक्स i से k + 1) * arr के सबऐरे का अधिकतम k + 1 से j + 1
memo[(i, j)] := res
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]