C++ में स्टोन्स को मर्ज करने की न्यूनतम लागत

मान लीजिए कि हमारे पास एक पंक्ति में व्यवस्थित पत्थरों के एन ढेर हैं। यहाँ i-वें ढेर में पत्थर हैं [i] पत्थरों की संख्या। एक चाल में K लगातार ढेर को एक ढेर में विलय करना होता है, अब इस चाल की लागत इन K संख्या के ढेर में पत्थरों की कुल संख्या के बराबर है। हमें पत्थरों के सभी ढेरों को एक ढेर में मिलाने के लिए न्यूनतम लागत का पता लगाना होगा। अगर ऐसा कोई समाधान नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट [3,2,4,1] और के =2 जैसा है, तो आउटपुट 20 होगा, ऐसा इसलिए है, क्योंकि हम [3, 2, 4, 1] से शुरू करेंगे। फिर हम 5 की लागत पर [3, 2] का विलय करते हैं, और हमारे पास [5, 4, 1] रह जाता है। उसके बाद हम 5 की लागत पर [4, 1] का विलय करते हैं, और हमारे पास [5, 5] रह जाता है। फिर हम 10 की लागत के लिए [5, 5] विलय करते हैं, और हमारे पास [10] रह जाता है। तो, कुल लागत 20 थी, और यह न्यूनतम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=पत्थरों का आकार

• अगर (एन -1) मॉड (के -1) 0 के बराबर नहीं है, तो -

  • वापसी -1

• आकार n + 1 के सरणी उपसर्ग को परिभाषित करें

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • उपसर्ग [i]:=उपसर्ग [i - 1] + पत्थर [i - 1]

• आकार n x n के एक 2D सरणी dp को परिभाषित करें

• आरंभिक लंबाई के लिए:=k, जब लंबाई <=n, अद्यतन (लंबाई 1 से बढ़ाएं), करें -

  • प्रारंभ करने के लिए i:=0, j:=लंबाई -1, जब j

  • डीपी [i, जे]:=inf

  • मध्य प्रारंभ करने के लिए:=i, जब मध्य

    • dp[i, j] :=न्यूनतम dp[i, j] और dp[i, mid] + dp[mid + 1, j]

  • अगर (j - i) mod (k - 1) 0 के समान है, तो -

    • dp[i, j] :=dp[i, j] + उपसर्ग[j + 1] - उपसर्ग[i]

• वापसी डीपी [0, एन -1]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,1};
   cout << (ob.mergeStones(v, 2));
}

इनपुट

{3,2,4,1}, 2

आउटपुट

20