資料結構
網路
關係資料庫管理系統 (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次檢視
廣告