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

समस्या विवरण

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

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

ट्री की लागत ट्री में हर नोड के लिए (b - a) के योग के रूप में निर्धारित होती है। हमारा लक्ष्य एक संभव ट्री की न्यूनतम संभव लागत निर्धारित करना है।

उदाहरण के लिए, यदि इनपुट है breakpoints = [1, 4, 7, 12], तो आउटपुट 28 होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

n := ब्रेकपॉइंट्स इनपुट ऐरे का आकार
यदि n ≤ 1, तो 0 वापस करें
यदि n = 2, तो breakpoints[1] - breakpoints[0] वापस करें
आकार n-1 का एक ऐरे p परिभाषित करें
i := 0 से n-2 तक के लिए, p[i] := breakpoints[i+1] - breakpoints[i]
आकार n का एक प्रीफिक्स योग ऐरे pre परिभाषित करें
i := 1 से n-1 तक के लिए, pre[i] := pre[i-1] + p[i-1]
आकार n×n का एक 2D DP ऐरे परिभाषित करें और इसे अनंत से आरंभ करें
आकार n×n का एक 2D ऐरे op परिभाषित करें
i := 1 से n-1 तक के लिए, dp[i][i] := p[i-1], op[i][i] := i
len := 2 से n-1 तक के लिए:
- i := 1 से n-len तक के लिए:
  - j := i + len - 1
  - idx := i
  - k := max(i, op[i][j-1]) से min(j-1, op[i+1][j]) तक के लिए:
    - cost := dp[i][k] + dp[k+1][j]
    - यदि cost < dp[i][j], तो idx := k, dp[i][j] := cost
  - op[i][j] := idx
  - dp[i][j] := dp[i][j] + pre[j] - pre[i-1]
dp[1][n-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}