[LeetCode/리트코드] #96. Unique Binary Search Trees[파이썬(python)/C++/BST]

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

Unique Binary Search Trees - LeetCode

BST(Binary Search Tree)는 root노드의 왼쪽으로는 더 작은 값, 오른쪽으로는 더 큰 값을 가지는 트리다. 

그래서 탐색 순회하기 효율적인 자료구조를 가진다. 

 

노드의 개수를 입력으로 받았을 때

만들 수 있는 BST의 개수를 출력으로 하면 된다. 

 

점화식을 이용하여 풀면 시간복잡도가 굉장히 좋게 결과가 나온다. 

 

 

파이썬 코드

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0]*20
        
        dp[0]=1
        dp[1]=1
        
        for i in range(2,n+1):
            for j in range(1,i+1):
                dp[i]=dp[i]+dp[j-1]*dp[i-j]
        return dp[n]

C++ 코드

class Solution {
public:
    int numTrees(int n) {
        int dp[20]={0,};
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            for(int j=1;j<i+1;j++){
                dp[i]=dp[i]+dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
        
    }
};