给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

一开始看到这道题没什么思路，先试着从1开始画出所有二叉搜索树来看看有没有规律。

观察n=3时画出的二叉搜索树，可以发现：

根节点固定时，二叉搜索树数量就等于n=左子树节点数量时二叉搜索树数量乘以n=右子树节点数量时二叉搜索树数量。

定义数组dp，dp[i]代表1到i组成的二叉搜索树数量。当n=i时，以j为根节点的二叉搜索树数量为dp[j-1]*dp[i-j]，j-1为左子树节点数量，i-j为右子树节点数量。dp[0]为多少呢？为了不让两边相乘为0，dp[0]当然为1，并且没有节点也可以理解为一种二叉搜索树。

所以只需要遍历1到i，让1到i都成为一次根节点，算出每次的二叉搜索树数量并且加起来：dp[i]+=dp[j-1]*dp[i-j]就得到了dp[i]。

要算出dp[n]，就要从前往后遍历依次算出dp[i]，因为后面的计算依赖于前边的结果。