该程序计算我们可以放置不重叠边缘以连接C ++中所有节点的方式的数量

假设我们有一个数字n，它表示循环放置的节点数。我们必须找到可以放置n / 2条边的方法，以使每个节点都由一条边连接，并且各边不会相交。如果答案很大，则返回结果mod 10 ^ 9 + 7。

因此，如果输入像n = 4，那么输出将是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);
}

输入值

4

2