[LeetCode] 96. Unique Binary Search Trees

😎풀이

주석으로 설명해두었지만, 가장 중요한 핵심은 Binary Search Tree의 특성을 잘 파악하고 있냐 이다.

현재 노드를 기준으로 왼 편에는 더 작은 수가, 오른 편에는 더 큰 수가 와야 한다는 기본 개념을 안다면 동적 프로그래밍으로 쉽게 풀이가 가능하다.

function numTrees(n: number): number {
    // dp 배열 초기화: dp[i]는 i개의 노드로 만들 수 있는 유니크한 BST의 개수
    const dp: number[] = new Array(n + 1).fill(0);
    
    // 기본 케이스: 빈 트리(노드 0개)와 노드 1개인 경우는 1가지 방법만 있음
    dp[0] = 1;
    dp[1] = 1;
    
    // 2부터 n까지의 각 크기에 대해 계산
    for (let i = 2; i <= n; i++) {
        // j를 루트 노드로 사용할 때 (1부터 i까지)
        for (let j = 1; j <= i; j++) {
            // 현재 노드(j)를 루트로 했을 때의 경우의 수 계산
            // 핵심 개념으로 BST는 현재 노드의 왼편에는 더 작은 수가, 오른 편에는 더 큰 수가 와야한다.
            // 왼쪽 서브트리의 경우의 수 * 오른쪽 서브트리의 경우의 수
            // 왼쪽: j-1개의 노드로 만들 수 있는 경우의 수
            // 오른쪽: i-j개의 노드로 만들 수 있는 경우의 수
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    
    return dp[n];
}