Unique Binary Search Trees(Math,Dynamic Programming,Tree,Binary Search Tree,Binary Tree)

https://leetcode.com/problems/unique-binary-search-trees/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.

 

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 19

그래도 가볍게나마 BST문제도 풀어봐야지..!

 

Linked List , Tree 이런 걸 자꾸만 건들자

 

근데 이건,, Tree 문제라기보단 수학 문제 같다..

 

흐

음..

 

 

1. Python

 

일단 애매하게.. 해결하지 못했다.

class Solution:
    def numTrees(self, n: int) -> int:
        if n == 1 : return 1
        ans = 0
        idx = n//2
        curr = n
        if n % 2 == 0 :
            while idx >= 1:
                curr-=1
                idx-=1
                ans += self.numTrees(curr)
        else:
            while idx >= 1:
                curr-=1
                idx-=1
                ans += self.numTrees(curr)
            ans += (self.numTrees(curr-1)*self.numTrees(curr-1))
        return ans

 

나름의 논리에는 문제가 없어 보이는데, 어딘가에서 ERROR가 나는지 자꾸 정답이 틀린다.

 

모범답안은 아래와 같다.

 

class Solution:
    def numTrees(self, n: int) -> int:
        # DP 배열 초기화
        dp = [0] * (n + 1)
        dp[0] = 1  # C_0 = 1
        dp[1] = 1  # C_1 = 1
        
        # 점화식 계산
        for i in range(2, n + 1):
            for j in range(1, i + 1):  # 각 i에 대해 C_{i-1} * C_{n-i} 계산
                dp[i] += dp[j - 1] * dp[i - j]
        
        return dp[n]

 

DP로도 풀 수 있다..

 

이렇게 Python function 안에 function을 선언하는 방법을 잘 참고해야겠다..!

class Solution:
    def numTrees(self, n: int) -> int:
        # 동적 계획법을 위한 캐싱
        memo = {}

        def count_trees(k):
            # 기저 조건
            if k <= 1:
                return 1
            if k in memo:  # 이미 계산된 값이 있으면 반환
                return memo[k]
            
            # 카탈란 수 점화식 계산
            total = 0
            for i in range(1, k + 1):
                left_trees = count_trees(i - 1)  # 왼쪽 서브트리 경우의 수
                right_trees = count_trees(k - i)  # 오른쪽 서브트리 경우의 수
                total += left_trees * right_trees
            
            memo[k] = total  # 결과를 캐시에 저장
            return total
        
        return count_trees(n)

 

대단하다 대단해..!

 

이거는 구찮으니까 C++로 memoization 한 번 해보는 것으로..!

 

2. C++

class Solution {
public:
    int numTrees(int n) {
        map<int,int> m;
        return cnt(n,m);
    }

    int cnt(int k, map<int,int>& m){
        if(k<=1) return 1;
        if(m.find(k)!=m.end()){ // how to use 'find' method in MAP(C++)
            return m[k];
        }
        int total = 0;
        for(int i=1;i<=k;i++){
            int left = cnt(i-1,m);
            int right = cnt(k-i,m);
            total += left*right;
        }
        m[k] = total;
        return total;
    }
};