不同的二叉搜索树

给你一个整数 n，求恰由 n 个节点组成、且节点值为 1 ~ n 的二叉搜索树共有多少种？返回满足条件的不同二叉搜索树的数量。

约定

• 节点值互不相同。
• 两棵树不同，当且仅当结构或某个节点的左/右孩子不同。

输入

• n：节点数，1 <= n <= 19。

输出

整数，表示不同 BST 的数量。

示例一

输入：

n = 3

输出：

5

示例二

输入：

n = 1

输出：

1

复杂度要求

• 时间 O(n^2)，空间 O(n)。