โปรแกรมนับจำนวนวิธีที่เราสามารถวางขอบที่ไม่ทับซ้อนกันเพื่อเชื่อมต่อโหนดทั้งหมดใน C++

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

ดังนั้นหากอินพุตเป็น n =4 เอาต์พุตจะเป็น 2 เนื่องจากเราสามารถจัดกลุ่มได้ดังนี้ -

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

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

• dp[0] :=1, dp[1] :=1

• ม :=10^9+7

• สำหรับการเริ่มต้น i :=2 เมื่อฉัน <=n / 2 อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สูง :=ผม

  • dp[i] :=0

  • สำหรับการเริ่มต้น j :=1 เมื่อ j <=สูง / 2 อัปเดต (เพิ่ม j ขึ้น 1) ทำ -

    • dp[i] :=(dp[i] + (2 * dp[j - 1] * dp[high - j])) mod ม

  • ถ้า % 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