DP를 사용하는 알고리즘들 #3

Optimal Binary Search Tree

 

Solution 1

: n 개의 key 를 가지는 가능한 모든 BST 를 생성하여, 그 중 total search cost 가 최소인 것을 고르기.

- n 개의 node 를 가진 BST 는 대략 O(4n) 개 정도 된다 à exponential time !

 

Solution 2 : Dynamic programming approach

1.Subproblem 정의 : 임의의 1 ≤ i ≤ j ≤ n 에 대해 C (i, j) 를 전체 key ki, ki+1, …, kj 을 각각 fi, fi+1, …, fj 번 검색한다 할때, optimal BST 의 total search cost 라고 하자. 따라서 C (1, n) 이 우리가 원래 구하고자 하는 optimal BST 의 total search cost 가 된다.

2. Recurrence relation 정의하기

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define MAX 100
int C[MAX][MAX] = {0};
int FLAG[MAX][MAX] = { 0 };
int f[MAX] = {0};
int opt_search_tree(int i, int j)
{
	if (FLAG[i][j] != 0) {
		return C[i][j];
	}
	else {
		if (i > j) {
			return 0;
		}
		else if (i == j) {
			return f[i];
		}
		else if (i < j) {
			int p = i;		//i~j까지 수 대체
			int sum = 0;	//시그마 Fp
			int mini = 0;	//최소값 구함
			for (p; p <= j; p++)
				sum += f[p];
			p = i;
			for (p; p <= j; p++) {
				if (mini == 0) {	//최소 값이 비어있을 때
					mini = C[i][p - 1] + C[p + 1][j];
					FLAG[i][j] = p;
				}
				else {	//나머지 최솟값을 찾아서 FLAG에 넣어줌
					if (mini > C[i][p - 1] + C[p + 1][j]) {
						mini = C[i][p - 1] + C[p + 1][j];
						FLAG[i][j] = p;
					}
				}
			}
			return mini + sum;
		}
	}
}