数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：计算连接所有节点的非重叠边的方法数
假设我们有一个数字n，表示圆形排列的节点数。我们必须找到可以放置n/2条边的方案数，使得每个节点都通过一条边连接，并且这些边不会相互交叉。如果答案非常大，则返回结果模10^9 + 7。
因此，如果输入为n = 4，则输出为2，因为我们可以将它们分组如下：
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为(n/2 + 1)的数组dp
dp[0] := 1, dp[1] := 1
m := 10^9+7
初始化i := 2，当i <= n / 2时，更新（i加1），执行：
high := i
dp[i] := 0
初始化j := 1，当j <= high / 2时，更新（j加1），执行：
dp[i] := (dp[i] + (2 * dp[j - 1] * dp[high - j])) mod m
如果high % 2不为零，则：
dp[i] := (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) mod m
dp[i] := dp[i] mod m
返回dp[n / 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
更新于：2020年12月22日
76次查看
广告