该程序计算我们可以放置不重叠边缘以连接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
热门推荐
10 医院探望朋友祝福语简短
11 毕业祝福语简短女朋友
12 春节虎年爸妈祝福语简短
13 儿童毕业祝福语 简短6
14 开工仪式横幅祝福语简短
15 孩子日常祝福语大全简短
16 清晨寄语诗句祝福语简短
17 结婚送亲认亲祝福语简短
18 虎年喝酒拜年祝福语简短