Chương trình đếm số cây tìm kiếm nhị phân duy nhất có thể được tạo với các giá trị từ 0 đến n trong Python

Giả sử chúng ta có một số n, chúng ta phải tìm số BST duy nhất mà chúng ta có thể tạo ra với các số từ [0, n). Nếu câu trả lời là rất lớn, mod kết quả là 10 ^ 9 + 7

Vì vậy, nếu đầu vào là n =3, thì đầu ra sẽ là 5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• numer:=1
• denom:=n + 1
• đối với tôi trong phạm vi từ 1 đến n, thực hiện
  • numer:=numer * n + i
  • numer:=numer mod m
  • denom:=denom * i
  • denom:=denom mod m
• numer:=numer * (denom ^ (m-2)) mod m
• trả về số mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

4

Đầu ra

14