Python Solution Using DP

  • 0

    Apparently, any BST in size of n will have n partitions, for example [0,...i ], i+1, [i+2,...n]. where i+1 represent the root.

    Then we can simply reduce the question. Here's the code


    def numTrees(self, n):
            :type n: int
            :rtype: int
            if n == 0: return 0
            dp = [0 if _ > 1 else 1 for _ in xrange(n+1)]
            for i in xrange(2, n+1):
                for j in xrange(0, i):
                    dp[i] += dp[j] * dp[i-1-j]
            return dp[-1]
    # 79 ms

Log in to reply

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