Simple DP Solution 84.6%


  • 0
    C
    def numTrees(self, n):
        if n < 2:
            return n
        dp = [ 0 for i in range(n + 1)]
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            mid = i // 2
            for j in range(0, mid):
                dp[i] += (dp[j] * dp[i-1-j]) * 2
            if i % 2 == 1:
                dp[i] += dp[mid] ** 2
        return dp[-1]

Log in to reply
 

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