96. Unique Binary Search Trees

# Medium

Dynamic Programming. Build dp[n+1] to record how many unique BST until ith. dp[i] = sum(dp[smaller than root]*dp[greater than root]), root is changing.

mums of trees = dp[smaller than root]*dp[greater than root]

Solution:

1. Initialize dp[n+1], dp[0]=1. Think about how to compute d[i] and the value of dp[1] should be.

2. Move root until ith, sum all of the possible roots, then get dp[i].

3. Return dp[n]

Python

class Solution:
    def numTrees(self, n: int) -> int:
        # initialize dp[i], dp[i] means number of trees until i
        dp = [1]*(n+1)
        
        # regular case
        for i in range(1, n+1):
            num = 0
            for j in range(1, i+1):
                root = j
                smaller = root-1
                greater = i-root
                num = num + dp[smaller]*dp[greater]
            dp[i] = num
            
        return dp[n]
                

Second Tab

Time complexity = $O(n^2)$ , space complexity = $O(n)$