LeetCode 96 unique BST

96. Unique Binary Search Trees

leetcode 96번 문제를 리뷰 해보도록 하겠습니다. 중요한 키포인트만 잡고 세세한 부분은 넘어가도록 하겠습니다.

Description

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

key point

이 문제는 DP로 풀 수 있습니다. 임의의 데이터 집합에 대한 모든 가능한 Datastructure를 구하는 문제이기 때문에 , DataStructure의 operation이나 정의를 적용하여 풀 수 없습니다. 하지만, DP를 적용할 때 symmetric인지 아닌지를 구별 안하면 좀 더 간결한 풀이가 그낭합니다. 여기서 , 수학적 지식이 더해진다면 100명중 1명의 개발자가 될 수 있습니다. (leetcode 속도 시스템은 잘 모르겠습니다.어제는 하위 10퍼엿는데 오늘 다시 제출해보니까 상위 1퍼네요..머죠?)

Solution 1

class Solution:
    dp = []
    def cal_dp(start , end )  :
        sum = 0
        if start >= len(Solution.dp) or end <0 :
            return 1
        if Solution.dp[start][end] != -1:
            return Solution.dp[start][end]
        if start > end :
            return 1
        for i in range(start,end+1):
            sum += Solution.cal_dp(start,i-1) * Solution.cal_dp(i+1,end)
        Solution.dp[start][end]=sum       
        return sum
    def numTrees(self, n: int) -> int:
        Solution.dp  = [  [-1 for _ in range(n)] for _ in range(n)]
        for i in range(n) :
            Solution.dp[i][i] = 1
        Solution.cal_dp(0,n-1)
        return Solution.dp[0][n-1]

다. DP하면 f(n) = f(n-1) + f(n-2) 같은 유형을 단순히 외우고만 있엇기에 아무 고민 없이 2차원 배열을 정의 했습니다. Dp 풀이의 정석처럼 풀었습니다.

Solution 2

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0]*(n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]

G(n) 을 길이 n인 sequence로 만들 수 있는 BST의 개수라 정의하겠습니다. 저희가 풀려는 문제의 답입니다.

F(i,n) 을 i가 root 인 길이 n인 sequence로 만들 수 있는 BST의 개수라 정의하겠습니다.

이는 \(G(n) = \sum_{k=1}^n F(i,n)\) 로 정의된다고 볼 수 있습니다. \(F(i,n) = G(i-1) * G(n-i )\)가 됩니다.

\(G(n) = \sum_{k=1}^n G(i-1) G(n-i )\) 가 됩니다. 즉 , 순서대로 G(1) ,G(2) ,…G(n) 을 구하면 해를 구할수 있게 됩니다.

Solution 1 , Solution2 의 차이

저는 F(0, n-1) 이라는 문제를 정의해서 풀었습니다. F(0, n-1) 을 1…. n 사이의 숫자로 만든 모든 ? 개수라고 정의했습니다. 하지만, 숫자의 범위가 어디든 간에 n개의 연속된 숫자에 대한 BST의 개수는 항상 같습니다. 즉, 대칭성(symmetric)을 알아내지 못했기에 비효율적인 풀이를 작성하게 된 것입니다.

Solution 3

이 G(n)이라는 것은 Catalan number 라는 것으로 정의되어 있습니다.

\(C_(n+1) = \frac{2(2n+1)}{n+2} C_n\) 으로 정의가 됩니다.

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

이렇게 풀 수 있습니다.