题解 | #有多少个不同的二叉搜索树#

import sys

# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))

n = int(input())

dp =[0 for i in range(n+1)]
dp[0]=1
# i表示以i个节点有多少个二叉树
for i in range(1,n+1):
  #j表示以j为根节点的二叉树有几颗，以j为根节点将节点分为左边j-1个元素，和右边i-j个元素，j从1开始到i全部遍历
    for j in range(1,i+1):
        dp[i]+= dp[j-1]* dp[i-j]

print(dp[n])