โปรแกรมนับจำนวน BST ที่เป็นไปได้จาก n โหนดที่แตกต่างกันใน Python

ได้รับ n ต้องการนับจำนวน BST ที่แตกต่างกันที่สร้างจากค่า 1 ถึง n หากคำตอบใหญ่ให้โมดุลอ 10^9+7

ตัวอย่าง: n=3 ผลลัพธ์คือ 14 (แคตาลันนัมเบอร์ C_4 = 14)

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

ใช้ความสัมพันธ์เวียนเกิดของ Catalan numbers: C_{n+1} = 1 + Σ_{i=1}^{n} C_i * C_{n+1-i}

1. สร้างอาร์เรย์ a เริ่มต้น [0, 1]
2. คำนวณ Catalan numbers จนถึง max_n (1000) แล้วเก็บไว้
3. คืนค่า (a[n+1] - 1) % MOD

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

def solve(n):
    MOD = 10**9 + 7
    max_n = 1000
    a = [0, 1]
    for k in range(2, max_n + 2):
        a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % MOD)
    return (a[n + 1] - 1) % MOD

# ทดสอบ
n = 3
print(solve(n))  # ผลลัพธ์: 14

อินพุตตัวอย่าง

3

เอาต์พุตตัวอย่าง

14