不同的二叉搜索树（卡特兰数）-526互联

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

1. 动态规划

由于二叉搜索树是有序的，父节点值大于左子树，而小于右子树，所以选定根节点后会将集合划分为两部分
显然，左子树和右子树的构成同样也是个二叉搜索树个数问题，从而形成递推公式
dp[n]表示n个节点能构成的二叉搜索树个数，我们分别枚举1,2..n节点作为根节点
则dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-1] +....dp[n-1]*dp[0]

int numTrees(int n) {
    vector<int> dp(n+1);
    dp[0] = 1;
    dp[1] = 1;
    function<int(int)> f = [&](int num){
        if(dp[num]) return dp[num];
        int res = 0;
        for(int i=0;i<num;i++)
            res += f(i)*f(num-i-1);
        return dp[num] = res;
    };
    return f(n);
}

由小到大递推

int numTrees(int n) {
    vector<int> G(n + 1, 0);
    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            G[i] += G[j] * G[i-j-1];
        }
    }
    return G[n];
}

2. 卡特兰数拓展

排列数$$ A^{m}_{n} = \frac{n!}{(n-m)!} $$

组合数$$ C^{m}_{n} = \frac{n!}{(n-m)!m!} $$

上面的问题，是一种典型的卡特兰数计算$$ G（n） = \sum_1^n{G(i-1)*G(n-i)} $$

其和为$$ \frac{1}{n+1}C^{n}_{2n} = \frac{1}{n+1} * \frac{(2n)!}{n!n!}$$

故可以得到递推公式$$ C_{n+1} = \frac{2(2n+1)}{n+2} C_{n}$$

int numTrees(int n) {
    long long C = 1;
    for (int i = 0; i < n; ++i) 
        C = C * 2 * (2 * i + 1) / (i + 2);
    return (int)C;
}

3. 出栈顺序个数

对于另一个问题，将n个不同数放入栈中，求出栈顺序的个数
同样设dp[n]为对应个数，我们可以枚举不同数作为最后一个出栈的情况，记该数为第i个数
下标比这个数小的，在进栈前便已经出了栈，具体的顺序为dp[i-1]
下标比这个数大的，则是该数进栈后再进入的栈，具体顺序为dp[n-i]
然后将两个数相乘得到以该数为最后出栈数的顺序个数，最后枚举求和，同样是我们上面的卡特兰数

卡特兰codeforces nephren cinema