সি++-এ ক্রস না হওয়া হ্যান্ডশেক

ধরা যাক n সংখ্যক মানুষ (যে একটি জোড় সংখ্যা) একটি সার্কেলের চারদিকে দাঁড়িয়ে আছে এবং প্রতিটি মানুষ অন্য কারো সাথে হ্যান্ডশেক করে, তাই মোট n/2 হ্যান্ডশেক হবে। আমাদের সেই পদ্ধতির সংখ্যা খুঁজে বের করতে হবে যাতে হ্যান্ডশেকগুলো কোনোক্রমে একে অপরের সাথে ক্রস না করে। উত্তরটি খুব বড় হতে পারে তাই ans mod 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 <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)); }