পাইথনে লিফ ভ্যালু থেকে ন্যূনতম খরচ ট্রি নির্মাণ

মনে করুন আমাদের একটি পজিটিভ ইন্টিজার অ্যারে arr আছে। সকল বাইনারি ট্রি বিবেচনা করুন যাতে:

প্রতিটি নোডের ০ বা ২টি চাইল্ড থাকে;
arr অ্যারের ভ্যালুগুলো ইনঅর্ডার ট্রভার্সালে লিফ নোডগুলোর ভ্যালু;
প্রতিটি নন-লিফ নোডের ভ্যালু তার বাম ও ডান সাবট্রির সর্বোচ্চ লিফ ভ্যালুর গুণফল।

সকল সম্ভাব্য বাইনারি ট্রির মাঝ থেকে নন-লিফ নোডের ভ্যালুগুলোর যোগফল ন্যূনতম কত হতে পারে সেটি বের করতে হবে। ইনপুট arr = [6,2,4] হলে আউটপুট হবে 32। সম্ভাব্য দুটি ট্রি:

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (DP + মেমোইজেশন):

memo নামক একটি ম্যাপ বানান।
dp(i, j) মেথড ডিফাইন করুন:
- যদি j <= i, তবে 0 রিটার্ন করুন।
- যদি (i, j) memo-এ থাকে, তবে memo[(i, j)] রিটার্ন করুন।
- res := infinity
- for k in range i to j - 1:
  - res := min(res, dp(i, k) + dp(k+1, j) + max(arr[i:k+1]) * max(arr[k+1:j+1]))
- memo[(i, j)] := res
- return memo[(i, j)]
মেইন মেথড dp(0, len(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]