সি++-এ সমস্ত নোড সংযোগ করার জন্য আমরা ননওভারল্যাপিং প্রান্তগুলি স্থাপন করতে পারি তার সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে যা বৃত্তাকারভাবে স্থাপন করা নোডের সংখ্যাকে প্রতিনিধিত্ব করছে। আমরা n/2 প্রান্তগুলিকে কতগুলি উপায়ে স্থাপন করতে পারি তা খুঁজে বের করতে হবে যাতে প্রতিটি নোড একটি প্রান্ত দ্বারা সংযুক্ত থাকে এবং সেই প্রান্তগুলি একে অপরের সাথে ছেদ না করে। যদি উত্তরটি খুব বড় হয় তবে ফলাফল মোড 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি n =4 এর মত হয়, তাহলে আউটপুট হবে 2, আমরা নিচের মত তাদের গ্রুপ করতে পারি -

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন (n/2 + 1)
dp[0] :=1, dp[1] :=1
m :=10^9+7
আরম্ভ করার জন্য i :=2, যখন i <=n / 2, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
- উচ্চ :=i
- dp[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[(উচ্চ - 1) / 2] * dp[(উচ্চ - 1) / 2])) মোড m
- dp[i] :=dp[i] mod m
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];
}
main(){
   int n = 4;
   cout << solve(n);
}