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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
m := 10^9 + 7
आकार (n+1) का एक ऐरे dp परिभाषित करें
dp[0] := 1
i := 0 से शुरू करें, जब i <= n, i := i + 2 से अपडेट करें, करें:
j := 0 से शुरू करें, जब j <= i-2, j := j + 2 से अपडेट करें, करें:
dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)
dp[i] := dp[i] mod m
dp[n] mod m लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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 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;
}
};
int main() {
Solution ob;
cout << (ob.numberOfWays(2));
}
इनपुट
2
आउटपुट
1