Desription > Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? > Solutions 1. Recursive Solution Binary search tree의 정의를 이용해서 재귀적인 방식으로 풀어보자 1 <= i <= n인 i를 root로 하는 트리의 경우의 수는 left의 경우의 수 * right의 경우의 수와 같다. bst의 정의에 의해 left에 들어갈 수 있는 수는 i보다 작은 숫자들이고, 반대로 right에 들어갈 수 있는 수는 i보다 커야 한다. 그리고 base case로 자식 노드가 하나거나 없으면 경우의 수는 1이다. 2. DP Solution 특정 숫자가 root인 경우 실제 node의 좌측과 우측에 만들어질 수 있는 경우의 수는 결국 좌측과 우측에 할당 가능한 숫자들의 갯수가 중요하다. i개의 숫자