5 lines python DP


  • 0
    A
    class Solution(object):
        def numTrees(self, n):
            dp = [1, 1] + [0] * (n+1 - 2)
            for i in range(2, n+1): # fill in the dp table
                for j in range(1, i+1): # calc the actual data, loop j from 1 to n as root
                    dp[i] += dp[j-1] * dp[i-j]
            return dp[-1]

Log in to reply
 

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