Problem

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Algorithm

Dynamic Programming (DP).
States: dp(i, j) is the list of all the BST’s that can be constructed by the number from i to j.
Translation: d p ( i , j ) = d p ( i , k − 1 ) ∗ d p ( k + 1 , j ) dp(i, j) = dp(i, k−1) * dp(k+1, j) dp(i,j)=dp(i,k−1)∗dp(k+1,j)

Code

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [[0 for i in range(n+1)] for j in range(n+2)]
        
        for s in range(1, n+2):
            dp[s][s-1] = 1
        
        for L in range(1, n+1):
            for s in range(1, n-L+2):
                e = s+L-1
                for k in range(s, e+1):
                    dp[s][e] += dp[s][k-1] * dp[k+1][e]
                    
        return dp[1][n]