'''
Description: 
Autor: Au3C2
Date: 2021-03-25 14:51:04
LastEditors: Au3C2
LastEditTime: 2021-03-25 14:52:34
'''
class Solution:
    def numTrees(self, n: int) -> int:
        resList = [1,1,2]
        if n < 3:
            return resList[n]
        # res = 0
        for i in range(3,n+1):
            res = 0
            for j in range(1,i+1):
                res += resList[j-1] * resList[i-j]
            resList.append(res)
        return resList[-1]

# 树，动态规划
# https://leetcode-cn.com/submissions/detail/159620056/

# 或者用数学法👇，卡塔兰数
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)