C++에서 교차하지 않는 악수

<시간/>

원 주위에 서 있는 짝수 명의 사람이 있고 각 사람이 다른 사람과 악수한다고 가정하면 총 n/2회의 악수가 됩니다. 악수가 교차하지 않도록 이러한 악수가 발생할 수 있는 방법의 수를 찾아야 합니다. 답변이 매우 클 수 있으므로 답변 모드 10^9 + 7을 반환하십시오.

따라서 입력이 n =2와 같으면 출력은 1

이 됩니다.

C++에서 교차하지 않는 악수

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

m :=10^9 + 7
(n+1) 크기의 배열 dp 정의
dp[0] :=1
초기화 i :=0의 경우 i <=n일 때 i 업데이트 i :=i + 2, 수행 -
- 초기화 j :=0의 경우 j <=i-2일 때 j :=j + 2를 업데이트하고 -
  를 수행합니다.
  - dp[i] :=dp[i] + (dp[j] 모드 m * dp[i - 2 - j] 모드 m)
  - dp[i] :=dp[i] 모드 m
반환 dp[n] mod m

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9+7;
typedef long long int lli;
class Solution {
   public:
   int numberOfWays(int n) {
      vector <lli> dp(n+1);
      dp[0] = 1;
      for(int i = 0; i <= n; i+=2 ){
         for(int j =0 ; j <= i-2; j+=2){
            dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
            dp[i]%=m;
         }
      }
      return dp[n]%m;
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfWays(2));
}