Unique Binary Search Trees

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

Dynamic Programming

class Solution:
    def numTrees(self, n: int) -> int:
        self.cache = dict()
        self.cache[0] = 1
        def getNumTrees(num):
            if num in self.cache:
                return self.cache[num]
            ans = 0
            for i in range(1,num+1):
                ans += getNumTrees(i-1) * getNumTrees(num-i)
            self.cache[num] = ans
            return ans
        
        return getNumTrees(n)