LeetCode - Unique Binary Search Trees

Desription

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:
 Input: 3
 Output: 5
 Explanation:
 Given n = 3, there are a total of 5 unique BST's:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solutions

1. Recursive Solution

Binary search tree의 정의를 이용해서 재귀적인 방식으로 풀어보자
1 <= i <= n인 i를 root로 하는 트리의 경우의 수는 left의 경우의 수 * right의 경우의 수와 같다. bst의 정의에 의해 left에 들어갈 수 있는 수는 i보다 작은 숫자들이고, 반대로 right에 들어갈 수 있는 수는 i보다 커야 한다. 그리고 base case로 자식 노드가 하나거나 없으면 경우의 수는 1이다.

var numTrees = function(n) {
    return getCases(1, n);
};

function getCases(low: number, high: number): number {
  if (low >= high) return 1;
  
  let cases = 0;
  for (let i = low; i <= high; i++) {
    cases += getCases(low, i - 1) * getCases(i + 1, high);
  }
  return cases
}

2. DP Solution

특정 숫자가 root인 경우 실제 node의 좌측과 우측에 만들어질 수 있는 경우의 수는 결국 좌측과 우측에 할당 가능한 숫자들의 갯수가 중요하다. i개의 숫자가 좌측 또는 우측에 할당 가능할 때 만들 수 있는 조합의 수를 dp[i]라고 하면 아래와 같이 문제를 해결할 수 있다.

var numTrees = function(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; // 할당 가능한 숫자가 없을 때 경우의 수는 1
  
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      dp[i] += dp[j - 1] * dp[i - j];
    }
  }
  return dp[n];  	
};