Unique Binary Search Trees - Dynamic Programming

Unique Binary Search Trees - LeetCode

문제설명

1~n까지의 수가 있는 BST(Binary Search Tree)는 몇 종류가 있는가?

n = 3일때, 답은 5이다. (5가지 모양)

---

문제 해결 방안

직접 그림으로 그려서 규칙성을 찾아보던 중,
n=3일 때 root가 1이나 3이면 한쪽에 n=2일 때의 경우의 수가 포함이 된다는 것을 알았다.
그리고 root가 2인 경우에도 양쪽으로 1개씩 있는 n=1과 같은 상황임을 알았다.

그래서 다음과 같은 규칙성을 찾아냈다.

U(n) = 1부터 n까지 있는 BST의 유니크한 경우의 수.
0 <= k <= n - 1
일 때,

U(n) = U(0) * U(n - 1) + U(1) * U(n - 2) + ... + U(k) * U(n - k - 1) + ... + U(n-1) * U(0)
임을 알 수 있다.

---

소스 코드 (TypeScript)

function numTrees(n: number): number {
    // U(k)
    let uniques = [1, 1];
    
    for (let i = 2; i <= n; i++) {
        let sum = 0;
        
        for (let j = 0; j < i; j++){
            sum += uniques[j] * uniques[i - j - 1];
        }
        
        uniques.push(sum);
    }
    
    return uniques[n];
};

U(n)을 구하기 위해서 U(n-1)이 필요하므로, uniques에 U(k)를 담아가며 구하는 방식이다.