हैंडशेक जो C++ में क्रॉस नहीं करते हैं

मान लीजिए कि हमारे पास सम संख्या में n लोग हैं जो एक वृत्त के चारों ओर खड़े हैं और प्रत्येक व्यक्ति किसी और से हाथ मिलाता है, जिससे कुल n / 2 हैंडशेक होंगे। हमें यह पता लगाना होगा कि ये हैंडशेक कितने तरीकों से हो सकते हैं ताकि कोई भी हैंडशेक पार न हो। उत्तर बहुत बड़े हो सकते हैं इसलिए उत्तर मोड 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट n =2 जैसा है, तो आउटपुट 1

. होगा

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

मी :=10^9 + 7
आकार की dp सरणी परिभाषित करें (n+1)
डीपी [0] :=1
इनिशियलाइज़ करने के लिए i:=0, जब i <=n, अपडेट i :=i + 2, करें -
- इनिशियलाइज़ j :=0 के लिए, जब j <=i-2, j :=j + 2 को अपडेट करें, −
  करें
  - डीपी [i]:=डीपी [i] + (डीपी [जे] मॉड एम * डीपी [i - 2 - जे] मॉड एम)
  - डीपी [i]:=डीपी [i] मॉड एम
वापसी डीपी [एन] मॉड एम

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9+7;
typedef long long int lli;
class Solution {
   public:
   int numberOfWays(int n) {
      vector <lli> dp(n+1);
      dp[0] = 1;
      for(int i = 0; i <= n; i+=2 ){
         for(int j =0 ; j <= i-2; j+=2){
            dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
            dp[i]%=m;
         }
      }
      return dp[n]%m;
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfWays(2));
}