Unique Binary Search Trees

Source

• lintcode: Unique Binary Search Trees

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

Python

class Solution:
    # @paramn n: An integer
    # @return: An integer
    def numTrees(self, n):
        if n<=0:
            return 1
        G= [0 for _ in range(1+n)]
        G[0]=1
        G[1]=1

        for i in range(2, n+1):
            for j in range(i):
                G[i]+=G[j]*G[i-j-1]
        return G[n]

Reference

Unique Binary Search Trees