Unique Binary Search Trees

Unique Binary Search Trees

Catalan number version - 32ms

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 1
        for i in range(1, n + 1):
            ans = ans * (i + n) // i
        return ans // (n + 1)

test code

In [95]: s = Solution(); t = s.numTrees(3); print(t)
5

leet code

卡塔兰数