本题的题面如下：给定一个整数 n，求以 1 ...n为节点组成的二叉搜索树有多少种？
思考过程：
首先很容易想到，只有一个结点的时候，二叉搜索树只有一种。而有多个结点的时候，根节点的左右子树还是二叉搜索树。我们令n个结点的二叉搜索树的二叉搜索树的种数为。假设根节点的值为i,则左子树的结点为1至i-1,右子树的结点为i+1至n。显然，根节点为i的有n个结点的二叉搜索树的个数为
。那么显然，结点数为n的二叉搜索树的个数为
.
代码如下：
class Solution {
public:
int dp[1000];
int numTrees(int n) {
memset(dp,0,sizeof(dp));
dp[0]=1;
dp[1]=1;
for(int i = 2;i<=n;i++)
{
int sum = 0;
for(int j = 0;j<i;j++)
{
sum += dp[j]*dp[i-j-1];
}
dp[i]+=sum;
}
return dp[n];
}
};
