96. Unique Binary Search Trees

给定1到n的一个数列，问这些数能有有多种二叉搜索树的组合。
按照n=1,2,3,4举例子试试，就会发现其实这是一个卡塔兰数。
递推公式：
= 1
=

对应通项公式：
=
所以有对应两种解法，

class Solution:
    def numTrees(self, n: int) -> int:
        if n == 0 :
            return 1
        result = [0]*(n+1)
        result[0] = 1
        result[1] = 1
        for i in range(2, n+1):
            # print('i', i)
            for j in range(i-1, -1, -1):
                # print('j,i-j-1',j,i-j-1)
                result[i] += result[j]*result[i-j-1]
            # print('result',result)
        return result[n]
        

通项公式：

class Solution:
    def numTrees(self, n: int) -> int:
        if n == 0 :
            return 1
        result = 1
        a = 1
        b = 1
        for i in range(n+1, 2*n+1):
            a *= i
            b *= (i-n)
        result = a // ((n+1)*b)
        return result