Description:
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
问题大意：给一个整数n，计算出节点数为n的二叉查找树的种类。
这个题目最简单的思路应该是递归构造二叉查找树，让每个节点都成为根节点。这样时间复杂度较高。还有一种动态规划法。描述如下：
假如整个树有 n 个节点，根节点为 1 个节点，两个子树平分剩下的 n-1 个节点。
假设我们已经知道节点数量为 x 的二叉树有dp[x]种不同的形态。
则一颗二叉树左节点节点数量为 k 时，其形态数为dp[k] * dp[n - 1 - k]。
而对于一颗 n 个节点的二叉树，其两个子树分配节点的方案有 n-1 种：
(0, n-1), (1, n-2), ..., (n-1, 0)因此我们可以得到对于 n 个节点的二叉树，其形态有：
Sigma(dp[i] * dp[n-1-i]) | i = 0 .. n-1并且可以发现，dp数组有递推关系，我们可以使用递推或是记忆化搜索来实现。
边界条件为dp[0] = 1。
以上分析来源这里
Java代码：
public class Solution {
int[] rc;
public int numTrees(int n) {
rc = new int[n+1];
Arrays.fill(rc, 0);
return dp(n);
}
public int dp(int nodes) {
if(nodes <= 1)
return 1;
if(rc[nodes] != 0)
return rc[nodes];
int numTrees = 0;
for(int i=0; i<nodes; i++) {
numTrees += dp(i) * dp(nodes-i-1);
}
rc[nodes] = numTrees;
return numTrees;
}
}