class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = [0 for i in range(n+1)]
        ans[0] = 1
        for op in range(1, n+1):
            for i in range(op):
                ans[op] += ans[i]*ans[op-1-i]
            
        return ans[-1]