Python에서 고유한 이진 검색 트리의 수를 세는 프로그램은 0에서 n까지의 값으로 구성할 수 있습니다.

하나의 숫자 n이 있다고 가정하고 [0, n)의 숫자로 생성할 수 있는 고유한 BST의 수를 찾아야 합니다. 대답이 매우 큰 경우 결과는 10^9+7

따라서 입력이 n =3과 같으면 출력은 5

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 숫자:=1
• 명:=n + 1
• 1~n 범위의 i에 대해
  • 숫자 :=숫자 * n + 나
  • 숫자 :=숫자 모드 m
  • denom :=denom * i
  • denom :=denom 모드 m
• 숫자 :=숫자 * (denom^(m-2)) mod m
• 반환 번호 모드 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