C++에서 모든 노드를 연결하기 위해 겹치지 않는 가장자리를 배치할 수 있는 방법의 수를 계산하는 프로그램

<시간/>

원형으로 배치된 노드의 수를 나타내는 숫자 n이 있다고 가정합니다. 모든 노드가 모서리로 연결되고 모서리가 서로 교차하지 않도록 n/2개의 모서리를 배치할 수 있는 방법의 수를 찾아야 합니다. 답이 매우 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 n =4와 같으면 아래와 같이 그룹화할 수 있으므로 출력은 2가 됩니다. -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

(n/2 + 1) 크기의 배열 dp 정의
dp[0] :=1, dp[1] :=1
m :=10^9+7
initialize i :=2의 경우 i <=n / 2일 때 업데이트(i를 1만큼 증가), −
- 높음 :=나는
- dp[i] :=0
- j:=1 초기화의 경우 j <=high / 2일 때 업데이트(j를 1만큼 증가), −
  - dp[i] :=(dp[i] + (2 * dp[j - 1] * dp[high - j])) 모드 m
- 높은 % 2가 0이 아닌 경우 -
  - dp[i] :=(dp[i] + (dp[(높은 - 1) / 2] * dp[(높은 - 1) / 2])) 모드 m
- dp[i] :=dp[i] 모드 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);
}