Python에서 n개의 개별 노드를 사용하여 가능한 BST의 수를 찾는 프로그램을 생성할 수 있습니다.

<시간/>

숫자 n이 있다고 가정합니다. [1,2,...,n]과 같은 숫자가 있는 경우 이 n개의 값을 사용하여 구성할 수 있는 가능한 BST의 수를 계산해야 합니다. 답이 너무 크면 결과를 10^9+7로 수정합니다.

따라서 입력이 n =3과 같으면 출력은 14가 됩니다.

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

a :=값이 [0, 1]인 목록
m :=10^9+7
max_n :=1000
2~max_n + 1 범위의 k에 대해
- insert(1 + 목록의 모든 요소의 합(a[i] * a[k - i] for all i in range(1, k))) mod m at the end a
반환(a[n + 1] - 1) 모드 m

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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