Unique Binary Search Tree

Question

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?

Example Given n = 3, there are a total of 5 unique BST's.

1           3    3       2      1
 \         /    /       / \      \
  3      2     1       1   3      2
 /      /       \                  \
2     1          2                  3

Thoughts

reference

以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成 如果以 i 作为根节点，由基本的排列组合知识可知，其唯一 BST 个数为左子树的 BST 个数乘上右子树的 BST 个数

Solution

class Solution:
    # @paramn n: An integer
    # @return: An integer
    def numTrees(self, n):
        # write your code here
        if n < 0:
            return -1

        count = [ 0 for i in range(n+1)]
        count[0] = 1
        for i in range(1, n+1):
            for j in range(1, i+1):
                #j means the root position
                #loop from 1 to i
                count[i] += count[j-1] * count[i-j]

        return count[n]