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

मान लीजिए कि हमारे पास एक संख्या n है जो गोलाकार रूप से रखे गए नोड्स की संख्या का प्रतिनिधित्व करती है। हमें n / 2 किनारों को रखने के तरीकों की संख्या का पता लगाना होगा जैसे कि प्रत्येक नोड एक किनारे से जुड़ा हुआ है, और यह कि किनारे एक दूसरे के साथ प्रतिच्छेद नहीं करते हैं। अगर उत्तर बहुत बड़ा है तो परिणाम मोड 10^9 + 7 लौटाएं।

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

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

आकार की dp सरणी परिभाषित करें (n/2 + 1)
डीपी [0]:=1, डीपी [1]:=1
मी :=10^9+7
इनिशियलाइज़ i :=2 के लिए, जब i <=n / 2, अपडेट करें (i को 1 से बढ़ाएँ), करें -
- उच्च:=मैं
- डीपी [i] :=0
- इनिशियलाइज़ j :=1 के लिए, जब j <=high / 2, अपडेट करें (j को 1 से बढ़ाएँ), करें -
  - dp[i] :=(dp[i] + (2 * dp[j - 1] * dp[high - j])) mod m
- यदि उच्च% 2 शून्य नहीं है, तो -
  - dp[i] :=(dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2]) मॉड m
- डीपी [i]:=डीपी [i] मॉड एम
वापसी डीपी [एन / 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];
}
main(){
   int n = 4;
   cout << solve(n);
}