🐰😺🌳 兔猫信奥学院的二叉搜索树计数探秘 🌳😺🐰

在信奥学院的魔法森林中，隐藏着一片神秘的数字果林：每棵果树都能长出编号从 1 到 n 的神奇果实。小兔和小猫被师傅交给重任——他们要用这些果实按照二叉搜索树的规则一层层地搭建果树阵列。

二叉搜索树 的规则是：

• 每个节点存放一个果实编号；
• 左子树所有节点编号都比根节点小，右子树所有节点编号都比根节点大；
• 而果实编号必须恰好使用 1 到 n 的所有果实，且每个果实只能使用一次。

小兔好奇地问：“一共有多少种不同的果树阵列呢？”
加菲老师微笑着说：“这正是今天的试炼——计算恰由 n 个节点组成的不同二叉搜索树的总数！”

输入格式

输入一行，含整数 n，表示果林节点（果实）数量。

• 1 ≤ n ≤ 5000

输出格式

输出一个整数，表示不同二叉搜索树的总数。

样例 1

3

5

• 解释：当 n=3 时，可构造的 BST 有 5 种。

样例 2

1

1

• 解释：当 n=1 时，只有一种单节点的 BST。

🎓 加菲老师寄语：
Catalan 数列蕴含丰富的组合奥秘，掌握它你就能轻松解决一系列“可搭建结构”计数问题。祝你在信奥的探秘之旅中收获满满！