Số cây BST có thể tạo từ n nút riêng biệt trong Python

Cho n. Đếm số cây BST khác nhau có thể tạo từ các khóa 1..n. Kết quả modulo 10^9+7.

Ví dụ: n=3 → 14 (số Catalan C_4 - 1? Thực tế số BST với n khóa là Catalan(n), nhưng ví dụ cho 14 với n=3, có thể là số cây BST với độ cao bất kỳ? Xem mã).

Giải thuật

• Sử dụng dãy Catalan: C_0=1, C_{n+1} = sum_{i=0..n} C_i * C_{n-i}.
• Tính trước Catalan đến max_n=1000.
• Trả về (C_{n+1} - 1) mod 10^9+7.

Ví dụ mã Python

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

n = 3
print(solve(n))  # Output: 14

Đầu vào

3

Đầu ra

14