class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1]; //dp[i]表示n个节点组成的二叉搜索数的种数
        dp[1] = 1;
        dp[0] = 1;
        //递推公式：选定任意点i作为根节点，则左子树为[1,i-1];右子树为[i+1,n];
        //dp[i] = ∑(dp[i-1] * dp[n-i])
        // dp[1] = 1
        // 遍历顺序：从前向后
        for (int i = 2; i <=n; i++) { // 总共有多少个节点
            for (int j = 1; j <= i; j++) { // 选哪一个做根节点
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
       
        return dp[n]; 
    }
}