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，问有多少不同的二叉搜索树（二叉搜索树的节点的值为1到n）？
分析：1-n，以i（1 <= i <= n）作为二叉搜索树的根节点，那么1到i-1部分为该二叉搜索树的左子树部分，i+1到n部分为该二叉搜索树的右子树部分，那么以i为根节点的二叉搜索树总共有（1到i-1组成的左子树 总数）*（i+1到n组成的右子树 总数）。因此，1到n组成的二叉搜索树的总个数为 分别以1到n为根节点的二叉搜索树的 个数 总和。
记F（i，n）表示总元素个数为n，即1到n，以i为根节点的二叉搜索树的个数。G（j）表示给定整数为j时，二叉搜索树的总个数。
则F（i，n）=G（i-1）*G（n-i）
G（n）=F（1，n）+ F（2，n）+ F（3，n）+ ... + F（n-1，n）+ F（n，n）
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
用递归的方法，可以如下实现：
class Solution { public: int numTrees(int n) { if(n<=1) return 1; int sum=0; for(int i=1;i<=n;i++) { sum += numTrees(i-1)*numTrees(n-i); } return sum; } };
但是，由上面可知，存在多次重复计算，因此时间复杂度比较高，会超时。我们需要把中间结果保存下来，避免重复计算。
可以用动态规划实现。dp[i]表示给定i，有dp[i]个二叉搜索树，即上面所说的G（i）
class Solution { public: int numTrees(int n) { if(n<=1) return 1; vector<int> dp(n+1,0); dp[0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } };