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

[Thoughts]

这又是一道动态规划的题。看了http://blog.csdn.net/linhuanmars/article/details/24761459这里的思路，大意是它的数学模型刚好是一种叫卡特兰数的定义

这样就把问题划分为了子问题(动态规划解题的思路)

对于n个结点的二叉树，使用一个数组count[]，存储n+1个元素(包括C₀)

[Code]

public class Solution {    public int numTrees(int n) {        int[] count = new int[n+1];        count[0]=1;        count[1]=1;        for(int i=2;i<=n;i++){            for(int j=0;j<i;j++){                count[i]+=count[j]*count[i-j-1];            }        }        return count[n];    }}