[LeetCode] 96. Unique Binary Search Trees

Problem : https://leetcode.com/problems/unique-binary-search-trees/

Iterate all valid numbers and use each of them as root. Then calculate the number of valid left / right sub-tree.  Unique BST = Number of Valid Left Sub-Tree * Number Of Valid Right Sub-Tree

class Solution:
    def numTrees(self, n: int) -> int:
        
        @lru_cache(maxsize=None)
        def helper(start, end):
            if start >= end:
                return 1
            
            result = 0
            
            for i in range(start, end + 1):
                lefts = helper(start, i-1)
                rights = helper(i+1, end)
                
                
                result += lefts * rights
                  
            return result
        
        
        return helper(1, n)

Another top-down solution

class Solution:
    def numTrees(self, n: int) -> int:
        
        @cache
        def helper(x):
            if x == 0:
                return 1
            
            if x == 1:
                return 1
            
            result = 0
            
            for i in range(x):
                result += helper(i) * helper(x-i-1)
                
            return result
        
        return helper(n)

Bottom-up solution

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

        return dp[n]

Edited on 11/07/2021. Add the bottom-up solution.