[leetcode] 96. Unique Binary Search Trees

문제 설명

링크
n 개의 노드를 가지는 BST 개수 구하는 문제

접근 1 - DP

• n == 4 일때, 루트를 제외하고 left, right sub trees 의 개수는
  0 3
  1 2
  2 1
  3 0
• for 문을 돌면서 left * right 를 하면 됨
• 중복을 줄이기 위해 n // 2 번만 for 문 탐색
  

코드 1

    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 // 2):
                dp[i] += 2 * dp[j] * dp[i- 1 - j]
            if i % 2 == 1:
                dp[i] += dp[i//2] ** 2
        return dp[n]

접근 2 - Recursion

• 위와 접근은 동일하지만 for 문이 아닌 recursion 으로 구현
• memoization 이용

    def numTrees(self, n: int) -> int:
        self.table = [-1] * (n+1)
        self.table[0] = 1
        return self.numTreesRec(n)
        
    def numTreesRec(self, n):
        if self.table[n] != -1:
            return self.table[n]
        total = 0
        for m in range(n):
            total += (self.numTreesRec(n-1-m) * self.numTreesRec(m))
        self.table[n] = total
        return total