Python DP 35ms


  • 0
    Y
    def n_trees(n):
        # bottom up iterative computation, 7000% faster than recursive
        #
        # O(n^2) time?
        memo = {0: 1, 1: 1}
        for k in xrange(2, n+1):
            m, j = 0, 0
            while j <= k-j-1:
                l = memo[j]
                r = memo[k-j-1]
                p = l*r
                if j != k-j-1:
                    p *= 2
                m += p
                j += 1
            memo[k] = m
        return memo[n]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.