不同的二叉搜索树

思路

二叉搜索树的概念：左子树上所有结点的值小于根结点值，右子树所有结点的值大于根结点值，并且左右子树均为二叉搜索树（二叉排序树）

卡特兰数

代码

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i = 2; i < n + 1; i++)
            for(int j = 1; j < i + 1; j++) 
                dp[i] += dp[j-1] * dp[i-j];
        
        return dp[n];
    }
}