ধরুন আমাদের একটি সারিতে সাজানো পাথরের স্তূপ আছে। এখানে 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
আউটপুট
20