思路1 dp

G(n)表示输入n时，能构建多少棵不同的BST。两个特殊情况是n=0和n=1时，空树和一个节点的树都只有一种情况，所以G(0)=1, G(1)=1

F(i, n)表示以i为根结点，n的序列能构建多少棵不同的BST。我们可以得到

G(n) = F(1, n) + F(2, n) + ... + F(n, n)

而F(i, n)又可以分成左右子树情况种类的乘积，即

F(i, n) = G(i-1) * G(n-i), 1 <= i <= n

最后可以得到

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

最后计算的时候，要从小开始算