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
解题思路
刚看到这一题的时候一点思路没有，但是因为是二叉搜索树，所以有个关系是一定的：
i+1一定是在i的右子树上的。
这时候结合上面的例子中的5颗二叉搜索树，多看看可以发现：
可以根据根节点的值来计算相应的unique BST种类数。
另外，因为在dynamic-programming标签下，我们就直接按照动态规划的方式去解决问题：
* 先找到合适的通项公式的含义
* 然后推导出状态转移方程
* 然后实现代码
分析
我们按照上面说的思路来分析下例题。
定义d(i,j)的含义是：n=i，j为根节点时的unique BST种类数
定义p(i)的含义是：n=i时的unique BST种类数（其实这就是本题通项公式的含义）。所以必然有
-
正式分析开始，借用数学中的归纳法思想：
i=1：d(1,1)=1；p(1)=1。
-
i=2：
- 根节点为1（j=1）时，2肯定在1的右子树上，所以只有1种情况，d(2,1)=1
- 根节点为2（j=2）时，1肯定在2的左子树上，所以只有1种情况，d(2,2)=1
- p(2)=d(2,1)+d(2,2)=2
-
i=3：
- 根节点为1（j=1）时，那2,3一定在1的右子树上，2,3两个数去任意构成BST，这种情况和i=2时一样，所以d(3,1)=p(2)=p(i-1)=2
- 根节点为2（j=2）时，1必须在2左子树上，3必须在2右子树上，所以只有一种情况，d(3,2)=1
- 根节点为3（j=3）时，1,2一定在3的左子树上，1,2两个数去任意构成BST，这种情况和i=2时一样，所以d(3,3)=p(2)=p(i-1)=2
- p(3)=d(3,1)+d(3,2)+d(3,3)=2+1+2=5
- 这时候就能看出点转移方程的苗头了，我们继续分析
-
i=4：
根节点为1（j=1）时，那2,3,4一定在1的右子树上，2,3,4三个数任意构成BST，这种情况和i=3时一样，所以d(4,1)=p(3)=p(i-1)=5
根节点为2（j=2）时，1在2的左子树上，3,4一定在2的右子树上。1任意构成1个数字的BST子树，当然也就有p(1)种情况，而3,4两个数任意构成BST子树，则有p(2)种可能，因此这种情况会有以下种unique BST的可能：
再深入想以下，2的左右子树有几个元素？很明显：2的左子树应该有1个（元素为1）、右子树有2个（元素为3、4）。更通用地表达为：j的左子树元素个数为j-1个，j的右子树上元素个数为i-j个。所以左子树上数字独自构成的unique BST数为p(j-1)，右子树上数字独自构成的unique BST数为p(i-j)，因此：
同理，根节点为3（j=3）时，3的左子树上是1,2，右子树是4，所以d(4,3)=p(2)*p(1)=2
同理，根节点为4（j=4）时，4的左子树上是1,2,3，所以d(4,4)=p(3)=5
p(4) = 5 + 2 +2 + 5 = 14
在这里再回看一下i=3和i=4的分析，可以发现d(i,1)=d(i,i)，d(i,2)=d(i,i-1)，... d(i,j)的计算是对称的，所以要算出p(i)，只需要计算一半，乘以2就行了，当然这个只是一个优化点。
到这里其实已经找到了状态转移方程：
可以再代入i=5验证一下。
代码实现
状态转移方程推导出来之后，代码写起来就很简单了。申请个n+1长度的数组，把p[1]~p[n]都记录下来（），返回p[n]就好了。
public static int numTrees2(int n) {
int[] p = new int[n+1];
p[1] = 1;
for (int i = 2; i < n+1; i++) {
int mid = i / 2;
for (int j = 1; j <= mid; j++) {
if (j == 1) {
p[i] += 2 * p[i-1];
} else {
p[i] += 2 * p[j-1] * p[i-j];
}
}
if (i % 2 == 1) p[i] += p[i-(mid+1)] * p[i-(mid+1)];
}
return p[n];
}
