96. Unique Binary Search Trees

Solution 1: DP

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

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 2: DFS + Bitmap (Optimized)

class Solution:
    def dfs(self, n: int, isVisited) -> int:
        if isVisited[n]:
            return isVisited[n]

        totalNumOfTree = 0
        for i in range(n):
            numOfLftTree = self.dfs(i, isVisited)
            numOfRhtTree = self.dfs(n-i-1, isVisited)
            totalNumOfTree += numOfLftTree * numOfRhtTree
        isVisited[n] = totalNumOfTree
        return isVisited[n]
        
    def numTrees(self, n: int) -> int:
        isVisited = [1, 1] + (n-1)*[0]
        totalNumOfTree = self.dfs(n, isVisited)
        return totalNumOfTree

Time Complexity: O(N^3) // 不太確定，請大大指點 ( _ _ )
Space Complexity: O(N)

Reference

https://www.cnblogs.com/grandyang/p/4299608.html
https://ithelp.ithome.com.tw/articles/10213289