সমস্যা বিবরণ
Nটি পাথরের সমূহ একটি সারিয়ে আছে। i-তম সমূহে stones[i] পাথর। একムুভে Kটি সংলগ্ন সমূহ মার্জ করে একটি সমূহ তৈরি করা যায়, খরচ = সেসব সমূহের মোট পাথর। সব পাথর এক সমূহে মার্জ করার ন্যূনতম খরচ বের করতে হবে। অসম্ভব হলে -1 রিটার্ন করুন।
উদাহরণ
stones = [3,2,4,1], K = 2 → আউটপুট = 20
প্রক্রিয়া: [3,2]→5, [4,1]→5, [5,5]→10। মোট = 5+5+10 = 20।
সমাধান পদ্ধতি
- ডাইনামিক প্রোগ্রামিং (DP) ব্যবহার করা হয়।
- প্রিফিক্স সাম আরে ব্যবহার করে রেঞ্জ সাম O(1)-তে পাওয়া যায়।
- dp[i][j] = i থেকে j পর্যন্ত সমূহ মার্জ করার ন্যূনতম খরচ।
- K-১ এর গুণক বিচ্ছিন্নতা রক্ষা করতে হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1) != 0) return -1;
vector<int> prefix(n + 1);
for (int i = 1; i <= n; i++)
prefix[i] = prefix[i - 1] + stones[i - 1];
vector<vector<int>> dp(n, vector<int>(n));
for (int len = k; len <= n; len++) {
for (int i = 0, j = len - 1; j < n; i++, j++) {
dp[i][j] = INT_MAX;
for (int mid = i; mid < j; mid += k - 1)
dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
if ((j - i) % (k - 1) == 0)
dp[i][j] += prefix[j + 1] - prefix[i];
}
}
return dp[0][n - 1];
}
};
int main() {
Solution ob;
vector<int> v = {3,2,4,1};
cout << ob.mergeStones(v, 2);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {3,2,4,1}, 2
আউটপুট: 20
