Level：
Medium
题目描述：
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
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
思路分析：
动态规划的思想，二叉树有个性质，就是左子树的节点值都比根小，右子树的节点值都比根大，题目说明二叉树的节点值是从1到n，所以我们能够确定如果根为k，那么左子树的值是1到k-1，右子树的值是k+1到n。还有一点是，对于一个根来说，唯一二叉树的数量是其左子树的数量乘上右子树的数量，这是简单的乘法原理。并且左右子树的形态数量跟具体的数没有关系，只跟这个树里有多少个节点有关。而根可以选择从1到n的任意数，唯一二叉树的总数，就是根为1到n的树相加。所以该问题化简为以k为根，其唯一左子树和右子树各有多少，这就是动态规划问题了，我们建立一个数组dp[ i ]，代表节点数为i的唯一子树有多少个。显然dp[0]=dp[1]=1。
代码：
public class Solution{
public int numTrees(int n){
int []dp=new int[n+1]; //dp[i]代表的是节点数为i的唯一子树有多少个
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++){//表示一共有多少的节点
for(int j=0;j<i;j++){ //表示左子树有多少节点
dp[i]=dp[i]+dp[j]*dp[i-j-1];
}
}
return dp[n];
}
}