给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
参考：
python
# 0096.不同的二叉搜索树
class Solution:
def numTrees(self, n: int) -> int:
"""
动态规划， 时间O(n), 空间O(n)
从1到n, 每个元素都可以作为头结点，所有累加，同时，某个元素作为头结点时，
左右子树-元素数量-数量相乘为该元素做头结点的BST的数量
tips:
手动模拟节点数1/2/3的，总结规律
:param n:
:return:
"""
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1
for i in range(2, n+1):
for j in range(1, i+1): # 最多到i
dp[i] += dp[j-1] * dp[i-j] # j-1 + i-j = i-1 -> 左右子树节点数量
return dp[-1]
if __name__ == "__main__":
test = Solution()
print(test.numTrees(3))
golang
package dynamicPrograming
// 动态规划
func numTrees(n int) int {
dp := make([]int, n+1)
dp[0] = 1
for i:=1;i<=n;i++ {
for j:=1;j<=i;j++ {
dp[i] += dp[j-1] * dp[i-j]
}
}
return dp[n]
}