题解 | #有多少个不同的二叉搜索树#

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    int dp[20];
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2; i<20; i++) {
        dp[i] = 0;
        for (int j=0; j<i; j++) {
            dp[i]+=dp[j]*dp[i-1-j];
        }
    }
    int n;
    scanf("%d",&n);
    printf("%d\n",dp[n]);
}

在本题中：

设dp(n)表示有n个结点时二叉搜索树有多少种可能，则

Ⅰ.当（左子树+根节点）结点的个数为1时，左子树为空，右子树上有n - 1个结点，右子树的二叉搜索树个数为dp(n - 1)

Ⅱ.当（左子树+根节点）结点的个数为i(1 < i < n)时，左子树有i-1个结点，右子树有n-i个结点；左子树的二叉搜索树个数为dp(i-1),右子树的二叉搜索树个数为dp(n - i);由排列组合可知此时二叉搜索树总的个数为dp(i - 1) * dp(n - i)

Ⅲ.当（左子树+根节点）结点的个数为n时，右子树为空，左子树上有n - 1个结点，左子树的二叉搜索树个数为dp(n - 1)

所以，n个结点二叉搜索树的个数上述三个步骤的和。

递推公式：

dp(n)=dp(0)*dp(n-1)+dp(1)*dp(n-2)+dp(2)*dp(n-3)+…+dp(n-1)*dp(0)