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

1）结构的总数和存储的n个有序数没有关系。即存放的是1,2,3或5、6、9结果都是一样的；

2）n=0\1时，结果都为1；n个有序数。取不论什么一个作为根结点，该值左边的为左子树。右边的为右子树，

在这样的情况下。可能的结构总数为：左子树结构数*右子树结构数。所以原问题就被分解成了两个子问题；

3）将取n个有序数作为根结点的情况的结构问题相加。就可以得到原问题的解，但应注意的是，如：1、2、3

取1或3作为根结点的情况，结构数是同样的，即具有对称性；那么也要考虑到奇偶性；

4）可以被分解成同样的子问题，自己就行採用递归，本程序採用循环的方法。

*/

int numTrees(int n)

{

	vector<int> store;

	store.push_back(1);

	store.push_back(1);

	for(int i=2;i<=n;++i)

	{

		int tmp=0;

		for(int j=0;j<i/2;++j)

		{

			tmp+=2*store[i-1-j]*store[j];

		}

		if(i%2)

			tmp+=store[i/2]*store[i/2];

		store.push_back(tmp);

	}

	return store[n];

}