โปรแกรมนับจำนวน BST ที่ไม่ซ้ำกันที่สร้างได้จากค่า 0 ถึง n ใน Python

สมมติว่ามีตัวเลข n เราต้องหาจำนวน BST ที่ไม่ซ้ำกันที่สร้างได้จากตัวเลข [0, n) หากคำตอบใหญ่ มอดูลัส 10^9+7

เช่น ถ้าอินพุตคือ n = 3 ผลลัพธ์จะเป็น 5

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

• numer := 1, denom := n + 1
• for i ในช่วง 1 ถึง n
  • numer := numer * (n + i) mod m
  • denom := denom * i mod m
• numer := numer * (denom^(m-2)) mod m
• คืนค่า numer mod m

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

class Solution:
    def solve(self, n):
        m = 10 ** 9 + 7
        numer = 1
        denom = n + 1
        for i in range(1, n + 1):
            numer *= n + i
            numer %= m
            denom *= i
            denom %= m
        numer *= pow(denom, m-2, m)
        return numer % m

ob = Solution()
print(ob.solve(4))

อินพุต

4

เอาต์พุต

14