পাইথনে পাথর মার্জ করার জন্য সর্বনিম্ন খরচ খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি সারিতে সাজানো পাথরের স্তূপ আছে। এখানে i-th স্তূপে পাথর [i] সংখ্যক পাথর রয়েছে। একটি পদক্ষেপে K পরপর পাইলগুলিকে একটি স্তূপে একত্রিত করা হয়, এখন এই পদক্ষেপের খরচ এই K সংখ্যক পাইলের মোট পাথরের সংখ্যার সমান। সমস্ত পাথরের স্তূপকে এক স্তূপে একত্রিত করার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে। যদি এমন কোন সমাধান না থাকে, তাহলে -1 রিটার্ন করুন।

সুতরাং, ইনপুট যদি nums =[3,2,4,1], K =2 এর মত হয়, তাহলে আউটপুট হবে 20, কারণ, প্রাথমিকভাবে [3, 2, 4, 1] আছে। তারপর [3, 2] খরচ 5 এর সাথে মার্জ করুন এবং আমাদের আছে [5, 4, 1]। এর পরে [4, 1] খরচ 5 সহ মার্জ করুন এবং আমাদের আছে [5, 5]। তারপর খরচ 10 এর সাথে [5, 5] মার্জ করুন এবং আমাদের আছে [10]। সুতরাং, মোট খরচ ছিল 20, এবং এটি সর্বনিম্ন।

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

n :=সংখ্যার আকার
যদি (n-1) মোড (K-1) 0 না হয়, তাহলে
- রিটার্ন -1
dp :=one n x n অ্যারে এবং 0 দিয়ে পূরণ করুন
যোগফল :=n আকারের অ্যারে (n+1) এবং 0
দিয়ে পূরণ করুন
1 থেকে n রেঞ্জের জন্য, করুন
- যোগফল[i] :=যোগফল[i-1]+সংখ্যা[i-1]
K থেকে n রেঞ্জের দৈর্ঘ্যের জন্য, করুন
- 0 থেকে n-দৈর্ঘ্যের রেঞ্জের জন্য, করুন
  - j :=i+দৈর্ঘ্য-1
  - dp[i, j] :=অসীম
  - i থেকে j-1 এর মধ্যে t এর জন্য, K-1 দ্বারা প্রতিটি ধাপে আপডেট করুন, করুন
    - dp[i][j] =ন্যূনতম dp[i, j] এবং (dp[i, t] + dp[t+1, j])
  - যদি (j-i) mod (K-1) 0 এর মত হয়, তাহলে
    - dp[i, j] :=dp[i, j] + sums[j+1]-sums[i]
dp[0, n-1]
ফেরত দিন

উদাহরণ

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

import heapq
def solve(nums, K):
   n = len(nums)
   if (n-1)%(K-1) != 0:
      return -1
   dp = [[0]*n for _ in range(n)]
   sums = [0]*(n+1)
   for i in range(1,n+1):
      sums[i] = sums[i-1]+nums[i-1]
   for length in range(K,n+1):
      for i in range(n-length+1):
         j = i+length-1
         dp[i][j] = float('inf')
         for t in range(i,j,K-1):
            dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
         if (j-i)%(K-1)==0:
            dp[i][j] += sums[j+1]-sums[i]
   return dp[0][n-1]

nums = [3,2,4,1]
K = 2
print(solve(nums, K))

ইনপুট

[3,2,4,1], 2