Leetcode - 96. Unique Binary Search Trees

문제

1 ~ n 까지 값이 포함된 노드가 BST 가 되는 경우의 수를 구하라. 가령 n=3일때 총 5가지의 BST가 존재.

Input: n = 3
Output: 5

아이디어

n=4 -> [1,2,3,4] 일때

총 갯수 = {
    1이 루트일때 -> n=3 의 트리갯수
    2가 루트일때 -> n=1의 트리갯수 * n=2의 트리갯수
    3이 루트일때 -> n=2의 트리갯수 * n=1의 트리갯수
    4가 루트일때 -> n=3의 트리갯수
} 를 더하면 됨.

이를 수식으로 표현해보면 아래와 같은 규칙이 발견됨. 여기서 u[4]가 위의 계산결과가 됨. 해결 아이디어를 떠올리기 어려워서 솔루션을 조금 참고.

u[0] = 1
u[1] = 1
u[2] = u[1]*u[0] + u[0]*u[1]
u[3] = u[2]*u[0] + u[1]*u[1] + u[0]*u[2]
u[4] = u[3]*u[0] + u[2]*u[1] + u[1]*u[2] + u[0]*u[3]
u[5] = ...

해결 DP

Runtime: 0 ms, faster than 100.00% of C

int numTrees(int n){
    int uniq[20] = {};
    uniq[0] = 1;
    uniq[1] = 1;
    
    for (int tgt = 2; tgt <= n; tgt++) {
        for (int i = 0; i < tgt; i++) {
            uniq[tgt] += uniq[tgt - i - 1] * uniq[i];
        }
        
    }
    return uniq[n];
}