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

มี n โหนดวางวงกลม ต้องการวาด n/2 เส้นเชื่อม ทุกโหนดถูกเชื่อม 1 เส้น และเส้นไม่ทับซ้อน หาจำนวนวิธี mod 10⁹+7

ตัวอย่าง: n=4 → 2 วิธี (Catalan Number C₂ = 2)

ขั้นตอนการแก้ปัญหา

นี่คือ Catalan Numbers: C₀=1, C₁=1, Cₙ = Σ Cᵢ₋₁ × Cₙ₋ᵢ

ใช้ DP: dp[i] = จำนวนวิธีสำหรับ 2i โหนด dp[i] = Σ 2×dp[j-1]×dp[i-j] (j=1..i/2) + (ถ้า i คี่) dp[(i-1)/2]²

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    const int MOD = 1e9+7;
    vector<long long> dp(n/2 + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n/2; i++) {
        dp[i] = 0;
        for (int j = 1; j <= i/2; j++)
            dp[i] = (dp[i] + 2 * dp[j-1] * dp[i-j]) % MOD;
        if (i % 2)
            dp[i] = (dp[i] + dp[(i-1)/2] * dp[(i-1)/2]) % MOD;
    }
    return dp[n/2];
}

int main() {
    cout << solve(4); // 2
    return 0;
}

อินพุต

4

เอาต์พุต

2