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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

思路：

本题可采用动态规划解决。dp[ i ] 表示从 节点 1 到节点 i 分别作为根节点 所形成的二叉搜索树的种数之和。

确定递推公式：dp[ i ] += dp [ j -1 ] * dp[ i - j ]，其中 j 是当前作为根节点的节点，取值范围是 [ 1， i ]，当 节点 j 作为根节点时，其 左子树的节点个数为 j -1，所以左子树形成的二叉搜索树的种数为 dp[ j - 1 ]，其右子树的节点个数为 i - j，所以右子树形成的二叉搜索树的种数为 dp [ i - j ]，故节点 j 作为根节点时形成的二叉搜索树的种数为 dp[ j - 1] * dp[ i - j ]。

初始化时， 0 个节点 时令 dp[ 0 ] 为 1，表示一棵空树。 遍历顺序：由于 dp[ i ] 依赖 dp[ j-1 ] 和 dp [ i - j ]，所以要计算 dp[ n ]，则需要先计算 dp [ 1 ] ~ dp[ n- 1 ]，因此要从前往后依次遍历计算出每一个 dp [ i ]（1<= i <= n）。

代码：

class Solution {
    public int numTrees(int n) {
        //初始化 dp,dp[i]表示从节点1到节点i分别作为根节点组成的二叉搜索树的种数之和
        int[] dp = new int[n+1];
        //初始化dp[0]
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                //以 j 为根节点的二叉搜索树的左子树有 j-1 个节点，右子树有 i-j 个节点
                dp[i]+= dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}

参考：代码随想录