Python Solution:

class Solution:
    def numTrees(self, n):
        #type n: int
        #dp(i): the number of unique BST for i nodes
        #[1,2,3], [2,3,4] create same number of BST
        #f(j,i): the number of unique BST, where j is the root
        #1,2...,j-1,  j,  j+1,j+2,...,i
        #dp(j-1)          dp(i-j)
        #f(j,i)=dp(j-1)dp(i-j)
        #dp(i)=f(0,i)+f(1,i)+...+f(n,i)
        #     =dp(0)dp(i-1)+dp(1)dp(i-2)+...
        #for j in range(1, i+1): #i nodes
        #   dp[i] += dp[j-1] * dp[i-j]
        
        
        dp = [0]*(n+1)
        dp[0], dp[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]

        return dp[n]
    
    #Time complexity: O(n^2)
    #Space complexity: O(n)

 

Time Complexity: O(n^2)

Space Complexity: O(n)

Feeling tired? You can also try our free online no-installation required casual games: Here Please consider to follow my youtube channel to support me: