96. 不同的二叉搜索树

题目链接：

96. 不同的二叉搜索树

题目描述：

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

题目分析：

该题选择用动态分析，dp数组存放有i个节点时，所有的二叉搜索树的个数

题解：

int numTrees(int n) {// dp[i]存放i个节点能够组成的二叉搜索树的种数int dp[n+1];memset(dp, 0, sizeof(dp));dp[1] = 1;for(int i = 2; i <= n; i++){// j是左子树中节点的个数，j < i是因为减去了根节点的一个for(int j = 0; j < i; j++){// 如果左子树个数为0，则等于右子树中二叉搜索树的个数// 如果右子树个数为0，则等于左子树中二叉搜索树的个数// 否则等于左子树中二叉搜索树的个数j加上右子树中二叉搜索树的个数if(j == 0){dp[i] += dp[i-j-1];}else if(j == i-1){dp[i] += dp[j];}else{dp[i] += dp[j] * dp[i-j-1];}}}return dp[n];
}