[DP] Unique Binary Search Trees

n개의 노드가 주어졌을때 만들수 있는 BST의 조합 갯수를 구하는 문제이다.

Tree의 전형적인 재귀방식으로도 풀 수 있으나, 기본적으론 DP로 풀어낼 수 있다.

 

BTS는 크기에 따라 자연스레 노드가 배치된다.

그러니까 root node만 배치하고 갯수만 나누어주면, 각각의 경우의 수는 고정된다는 뜻이다.

 

예컨데 다음과 같이 세개의 원소가 주어진다고 해보자.

만약 특정원소를 root로 정한다면, 양옆에 BST를 만들 수 있는 경우의 수는(2개,0개) (1개,1개) (0개,2개)로 나누어지는 방식일것이다.

예컨데 n개의 원소가 존재하고, f(n) 을 n개로 만들 수 있는 BST의 수라고 한다면

f(n) =( f(n)*f(0) ) + ( f(n-1)*f(1) ) + ( f(n-2)*f(2) ) + ( f(n-3)*f(3) ) ..... 

이렇게 설정할 수 있다.

갯수만 나눠주면 자동으로 트리의 갯수가 정해지기 때문이다.

 

따라서 다음과 같이 풀어낼 수 있다