C++で交差しないハンドシェイク

円の周りに立っているn人が偶数で、各人が他の人と握手しているとすると、合計n/2回の握手があります。どのハンドシェイクも交差しないように、これらのハンドシェイクが発生する可能性のある方法の数を見つける必要があります。答えは非常に大きい可能性があるため、答えmod 10 ^ 9+7を返します。

したがって、入力がn =2の場合、出力は1になります

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7

• サイズ（n + 1）の配列dpを定義します

• dp [0]：=1

• 初期化i：=0の場合、i <=nの場合、更新i：=i + 2、do −

  • 初期化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));
}

入力

2

出力

1