मान लीजिए हमारे पास N पत्थरों के ढेर एक पंक्ति में व्यवस्थित हैं। यहां i-वां ढेर में stones[i] पत्थर हैं। एक चाल में K लगातार ढेरों को एक ढेर में मिलाया जाता है, इस चाल की लागत इन K ढेरों में पत्थरों की कुल संख्या के बराबर होती है। हमें सभी पत्थरों को एक ढेर में मिलाने की न्यूनतम लागत ढूंढनी है। यदि ऐसा कोई समाधान नहीं है, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट [3,2,4,1] है और K = 2, तो आउटपुट 20 होगा, क्योंकि हम [3, 2] को 5 की लागत से मिलाते हैं, फिर [4, 1] को 5 की लागत से, और अंत में [5, 5] को 10 की लागत से। कुल लागत 20 है।
हल करने का दृष्टिकोण
यह एक क्लासिक इंटरवल डीपी समस्या है:
यदि (n-1) % (k-1) != 0, तो मर्ज करना असंभव है, -1 वापस करें
त्वरित रेंज योग क्वेरी के लिए प्रीफिक्स योग सरणी की गणना करें
dp[i][j] = अंतराल [i, j] को वैध ढेरों में मर्ज करने की न्यूनतम लागत
लंबाई k से n तक के अंतराल के लिए पुनरावृति करें
चरण (k-1) में संभावित मध्य बिंदुओं का प्रयास करें
जब (j-i) % (k-1) == 0, वर्तमान मर्ज की लागत जोड़ें
उदाहरण
#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 length = k; length <= n; length++) {
for (int i = 0, j = length - 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