C++ में नॉन-ओवरलैपिंग एज से सभी नोड्स जोड़ने के तरीकों की संख्या गिनने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक संख्या n है जो सर्कुलर रूप से रखे गए नोड्स की संख्या को दर्शाती है। हमें n/2 एज रखने के तरीकों की संख्या ढूंढनी है ताकि हर नोड एक एज से जुड़ा हो, और एज एक-दूसरे को इंटरसेक्ट न करें। यदि उत्तर बहुत बड़ा है तो परिणाम मॉड 10^9 + 7 वापस करें।

उदाहरण के लिए, यदि इनपुट है n = 4, तो आउटपुट 2 होगा, क्योंकि हम उन्हें नीचे दिखाए अनुसार ग्रुप कर सकते हैं।

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

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

1. आकार (n/2 + 1) का एक ऐरे dp परिभाषित करें
2. dp[0] := 1, dp[1] := 1
3. m := 10^9+7
4. i := 2 से n/2 तक:
   • high := i
   • dp[i] := 0
   • j := 1 से high/2 तक:
     • dp[i] := (dp[i] + (2 * dp[j-1] * dp[high-j])) mod m
   • यदि high % 2 शून्येतर है:
     • dp[i] := (dp[i] + (dp[(high-1)/2] * dp[(high-1)/2])) mod m
   • dp[i] := dp[i] mod m
5. dp[n/2] वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    vector<long long> dp(n / 2 + 1);
    dp[0] = 1;
    dp[1] = 1;
    int m = 1000000007;
    for (int i = 2; i <= n / 2; i++) {
        int high = i;
        dp[i] = 0;
        for (int j = 1; j <= high / 2; j++) {
            dp[i] = (dp[i] + (2 * dp[j - 1] * dp[high - j])) % m;
        }
        if (high % 2) dp[i] = (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) % m;
        dp[i] %= m;
    }
    return dp[n / 2];
}

int main() {
    int n = 4;
    cout << solve(n);
}

इनपुट

4

आउटपुट

2