given n how many structurally unique bst s binary search trees that store values 1 n for 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 taking 1n as root respectively 1 as root of trees f0 fn1 f0 1 2 as root of trees f1 fn2 3 as root of trees f2 fn3 n1 as root of trees fn2 f1 n as root of trees fn1 f0 so the formulation is fn f0 fn1 f1 fn2 f2 fn3 fn2 f1 fn1 f0 type n int rtype int taking 1 n as root respectively 1 as root of trees f 0 f n 1 f 0 1 2 as root of trees f 1 f n 2 3 as root of trees f 2 f n 3 n 1 as root of trees f n 2 f 1 n as root of trees f n 1 f 0 so the formulation is f n f 0 f n 1 f 1 f n 2 f 2 f n 3 f n 2 f 1 f n 1 f 0 type n int rtype int
def num_trees(n):
    
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        for j in range(i+1):
            dp[i] += dp[i-j] * dp[j-1]
    return dp[-1]