题目链接：96. Unique Binary Search Trees
题目描述
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
简而言之：给定1...n这N个数，问有多少种构造BST的方案。
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
解题分析
（自己没想到，看的discuss，大神的解法，配上自己的理解，溜~）
这个题跟有一个DP的问题非常像，我先不说，大家可以猜一下。
首先如何划分树？先找到一个根节点，然后分成左右两堆，再将左右两堆依次建树。这也就是划分了子问题。那么我们需要用参数的形式来表示：dp[n]表示，有n个数的时候，可以构造的BST数目。
假设我们在k这个地方进行划分（也就是以k为根节点），那么左侧就是1~(k-1)，右侧也就是k+1~N，然后左右再去构造子树。所以现阶段我们得到了递推方程:
这个式子我们以n=4为例将其展开就是:
这个式子到底什么意思呢，就是说当有四个数字可以让我们拿来当根结点的时候，我们依次让1,2,3,4当根节点。
由于BST的顺序性，左<根<右。那么让1当根节点，1的左为空即dp[0]，1的右侧为{2,3,4}又是三个节点，所以为dp[3]。那么这样的组合也就是dp[0]*dp[3]。同理可以解释剩下的三项因式的含义。
而我们要求的是dp[n]，而求dp[n]之前需要知道 dp[0]~dp[n-1]。
从下至上求解问题：初始化dp[0]=dp[1]=1。(树为null也算一个树。)
这个问题跟剪绳子，跟IntegerBreak，都是相同的思路。感兴趣的可以看:IntegerBreak
题解
public int numTrees(int n) {
if (n <= 0) return 0;
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[i-j]*dp[j-1];
}
}
return dp[n];
}
