[LeetCode] 96. Unique Binary Search Trees

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

Unique Binary Search Trees - LeetCode

Unique Binary Search Trees - Medium

 

n이 주어졌을때, 1~n이 val로 들어가있는 n개의 노드를 BST로 배열하는 경우의 수를 구하는 문제다.

 

n을 4라고 생각해보자.

이 때, 루트노드에 올 수 있는 노드의 val은 1,2,3,4가 된다.

 

루트 val이 1일때, 왼쪽은 아무것도 못오고 오른쪽 자식에는 2,3,4가 올 수 있다.

루트 val이 2일때, 왼쪽은 1이 오고, 오른쪽 자식에는 3,4,가 올 수 있다.

루트 val이 3일때, 왼쪽은 1,2가 올 수 있고, 오른쪽 자식에는 4가 올 수 있다.

루트 val이 4일때, 왼쪽은 1,2,3이 올 수 있고, 오른쪽 자식에는 아무것도 올 수 없다.

 

노드의 val 자체는 중요하지 않다.

1,2,3 이나 1,2,4 나 경우의수는 똑같이 나오게 된다.

따라서, 구하는 경우의 수는 dp[0]=1이라 할때 dp[왼쪽자식에 올 수 있는 노드의 수] * dp[오른쪽 자식에 올 수 있는 노드의 수] 가 된다.

 

즉 n=4일때는,

root = 1=> dp[0] * dp[3]

root = 2=> dp[1] * dp[2]

root = 3=> dp[2] * dp[1]

root = 4=> dp[3] * dp[0]

이렇게 구해서 다 더해주면 된다.

 

전체 풀이 코드

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