การจับมือกันที่ไม่ข้ามใน C++

สมมุติว่ามีคนจำนวนคู่ n ยืนเป็นวงกลม และแต่ละคนจับมือกับคนอื่น เพื่อจะได้มี n / 2 การจับมือกันทั้งหมด เราต้องหาหลายวิธีที่การจับมือกันเหล่านี้อาจเกิดขึ้นได้ โดยที่ไม่มีการจับมือกัน คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืน mod 10^9 + 7

ดังนั้นหากอินพุตเท่ากับ n =2 เอาต์พุตจะเป็น 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7

• กำหนดขนาดอาร์เรย์ dp (n+1)

• dp[0] :=1

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <=n อัปเดต i :=i + 2 ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <=i-2 อัปเดต j :=j + 2 ทำ −

    • dp[i] :=dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)

    • dp[i] :=dp[i] mod 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));
}

อินพุต

2

ผลลัพธ์

1