该程序计算我们可以放置不重叠边缘以连接C ++中所有节点的方式的数量
假设我们有一个数字n，它表示循环放置的节点数。我们必须找到可以放置n/2条边的方法，以使每个节点都由一条边连接，并且各边不会相交。如果答案很大，则返回结果mod10^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