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

मान लीजिए कि हमारे पास अद्वितीय और क्रमबद्ध संख्याओं की एक सूची है जो एक स्ट्रिंग में ब्रेकपॉइंट का प्रतिनिधित्व करती है। हम इन नियमों से एक ट्री बनाना चाहते हैं -

ऐसे नोड हैं जिनका मान (ए, बी) है जहां ए और बी ब्रेकपॉइंट हैं। इसका मतलब है कि नोड स्ट्रिंग में इंडेक्स [ए, बी] से फैलता है।
रूट नोड प्रत्येक ब्रेकपॉइंट पर फैला हुआ है। (पूरी स्ट्रिंग)।
एक नोड के बाएँ और दाएँ बच्चे के स्पैन ऑर्डर किए गए, सन्निहित हैं, और इसमें पैरेंट नोड का स्पैन शामिल है।
ब्रेकप्वाइंट में लीफ नोड्स का इंडेक्स 'ए' का इंडेक्स ब्रेकप्वाइंट में 'बी' के इंडेक्स से पहले 1 होता है।

एक पेड़ की लागत पेड़ में प्रत्येक नोड के लिए बी - ए के योग के रूप में निर्धारित की जाती है। हमारा लक्ष्य एक व्यवहार्य पेड़ की न्यूनतम संभव लागत निर्धारित करना है।

इसलिए, यदि इनपुट ब्रेकप्वाइंट =[1, 4, 7, 12] जैसा है, तो आउटपुट 28 होगा।

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

n :=इनपुट ऐरे ब्रेकप्वाइंट का आकार
अगर n <=1, तो -
- वापसी 0
यदि n 2 के समान है, तो -
- वापसी विराम बिंदु[1] - विराम बिंदु[0]
एक सरणी परिभाषित करें p[n - 1]
इनिशियलाइज़ i :=0 के लिए, जब i
- p[i] :=ब्रेकप्वाइंट[i + 1]
पहले एक सरणी परिभाषित करें[n]
इनिशियलाइज़ करने के लिए मैं :=1, जब i
- पूर्व[i] :=पूर्व[i - 1] + p[i - 1]
एक 2D सरणी dp[n, n] परिभाषित करें और अनंत के साथ कॉलम प्रारंभ करें।
एक 2D सरणी op[n, n]
. परिभाषित करें
इनिशियलाइज़ करने के लिए मैं :=1, जब i
- डीपी [i, i]:=p [i - 1], op [i, i]:=i
इनिशियलाइज़ लेन के लिए :=2, जब लेन
- इनिशियलाइज़ i :=1 के लिए, जब i + len - 1
  - जे:=मैं + लेन - 1
  - आईडीएक्स:=मैं
  - प्रारंभ करने के लिए k :=अधिकतम (i, op[i,j-1]), जब k <न्यूनतम (j-1, op[i + 1, j]), अद्यतन (k को 1 से बढ़ाएं), करें -
    - लागत:=डीपी [i, के] + डीपी [के + 1, जे]
    - अगर लागत
      - आईडीएक्स:=के
      - डीपी [i, जे]:=लागत
  - op[i, j] :=idx
  - dp[i, j] :=dp[i, j] + pre[j] - pre[i - 1]
वापसी डीपी [1, एन -1]

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& breakpoints) {
   int n = breakpoints.size();
   if (n <= 1) return 0;
   if (n == 2) return breakpoints[1] - breakpoints[0];
      vector<int> p(n - 1);
   for (int i = 0; i < n - 1; ++i) p[i] = breakpoints[i + 1] - breakpoints[i];
      vector<int> pre(n);
   for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + p[i - 1];
      vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
      vector<vector<int>> op(n, vector<int>(n));
   for (int i = 1; i < n; ++i) dp[i][i] = p[i - 1], op[i][i] = i;
   for (int len = 2; len < n; ++len) {
      for (int i = 1; i + len - 1 < n; ++i) {
         int j = i + len - 1;
         int idx = i;
         for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
            int cost = dp[i][k] + dp[k + 1][j];
            if (cost < dp[i][j]) {
               idx = k;
               dp[i][j] = cost;
            }
         }
         op[i][j] = idx;
         dp[i][j] += pre[j] - pre[i - 1];
      }
   }
   return dp[1][n - 1];
}
int main(){
   vector<int> breakpoints = {1, 4, 7, 12};
   cout << solve(breakpoints) << endl;
   return 0;
}

इनपुट

{1, 4, 7, 12}