পাইথনের পাতার তালিকা থেকে ন্যূনতম গাছের যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। এই তালিকাটি একটি গাছের অভ্যন্তরীণ ট্রাভার্সালে পাতার নোডগুলির প্রতিনিধিত্ব করছে। এখানে অভ্যন্তরীণ নোডের 2টি সন্তান রয়েছে এবং তাদের মান বাম উপবৃক্ষের বৃহত্তম পাতার মান এবং ডান উপবৃক্ষের বৃহত্তম পাতার মানের গুণফলের সমান। আমাদের বৃক্ষের ন্যূনতম যোগফলের সাথে এর মানের যোগফল খুঁজে বের করতে হবে

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[৩, ৫, ১০], তাহলে আউটপুট হবে ৮৩।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

res :=সংখ্যায় সমস্ত উপাদানের যোগফল
সংখ্যার আকার> 1, do
- i :=সংখ্যার ন্যূনতম উপাদানের সূচক
- বামে :=সংখ্যা[i - 1] যখন i> 0 অন্যথায় অসীম
- ডান:=সংখ্যা[i + 1] যখন i <সংখ্যার আকার - 1 অন্যথায় অসীম
- res :=res + (ন্যূনতম বাম এবং ডান) * ith উপাদান সংখ্যা, তারপর সংখ্যা থেকে ith উপাদান মুছুন
রিটার্ন রিটার্ন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ কোড

class Solution:
   def solve(self, nums):
      res = sum(nums)
      while len(nums) > 1:
         i = nums.index(min(nums))
         left = nums[i - 1] if i > 0 else float("inf")
         right = nums[i + 1] if i < len(nums) - 1 else float("inf")
         res += min(left, right) * nums.pop(i)

      return res

ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums))

ইনপুট

[3, 5, 10]