[Algorithm] Dynamic Programming

동적계획법

• Divide & Conquer방식과 유사하나, 차이점은 다음과 같다.
  [DC]
  분할 -> 정복 -> 결합: 공유되는 문제도 다시 해결
  [DP]
  분할 -> 정복 -> 테이블에 해당 값 저장 -> 분할 된 문제에 적용
  저장된 결과를 사용하여 문제해결, 공유되는 문제는 다시 해결하지 않는다.
• DP는 상향식 접근 방법으로
  1. 문제의 해를 구할 수 있는 재귀적인 성질을 설정
  2. 작은문제 해결 후 큰 문제의 해를 table에 저장
  3. 크기가 작은 문제의 해를 table에 저장, 크기가 큰 문제를 효율적으로 해결한다.

이항계수 구하기
sol.1 recursion

int bio1(int n, int k)
{
	if(k == 0 || k ==n) return 1;
	return (bio(n-1, k-1) + bio(n-1, k));
}

time complexity -> 지수시간 알고리즘

sol.2 DP

int boi2(int n, int k)
{
	int B[MAX][MAX];
	
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= min(i,k); j++)
		{
			if(j == 0 || j == 1) B[i][j] = 1;
			else B[i][j] = B[i-1][j-1] + B[i-1][j];
		}
	}
}

최장 증가 부분 수열

// example
int S[MAX] = {INT_MIN, 9, 5, 2, 8, 7, 3, 1, 6, 4};
int longest_increasing_subseq(int s[])
{
	int i, j;
	int h[MAX] = {0, }, p[MAX] = {0, };
	
	for(int i = 1; i < MAX; i++)
		for(int j = 0; j < i; j++)
			if(s[i] > s[j] && h[i] < h[j] + 1)
			{
				h[i] = h[j] + 1;
				p[i] = j;
			}
			
	for(i = 0; i < MAX; i++)
		if(max < h[i])
		{
			swap(max, h[i]);
			index = i;
		}
	
	int lis[MAX];
	i = max;
	while(index != 0)
	{
		lis[--i] = s[index];
		index = p[index];
	}
	
}

숫자 삼각형

// MAX_LEVEL: K
// 2D Array a
int number_triangle(int a[][MAX], int k)
{
	int best[MAX][MAX] = {0, };
	int i, j;
	int max_result = INT_MIN;
	
	for(i = 1; i < MAX; i++)
		for(j = 0; j < i; j++)
			best[i][j] = a[i][j] + max(best[i-1][j-1], best[i-1][j]);
	for(i = 1; i <= k; i++)
		if(max_result < best[k][i]) max_result = best[k][i];
	return max_result;
}

// 편집거리

#define get_t(a,b) (((a)==(b)) ? (0) : (1))

int editDist(string S, string T)
{
	int i, j;
	
	int d[MAX][MAX] = {0, }, N, M;
	
	N = S.length();
	M = T.length();
	
	for(i = 0; i < N; i++)
		for(j = 0; j < M; j++)
		{
			if(j == 0) d[i][j] = i;
			else if(i==0) d[i][j] = j;
			d[i][j] = min(d[i-1][j] + 1, min(d[i][j-1] + 1, d[i-1][j-1] + get_t(S[i], S[j])));
		}
		
	return d[n][m];
}

int chainedMatrix(int d[], int n)
{
	int diagonal;
	int i, j, k;
	
	int m[MAX][MAX] = {0 ,};
	
	for(diagonal = 1; diagonal < n; diagonal++)
	{
		for(i = 1; i <= n - diagonal; i++)
		{
			j = i + diagonal;
			int min = 0;
			for(k = i; k < j - 1; k++)
			{
				if(min == 0 || min > m[i][k] + m[k+1][j] + d[i-1] * d[k] * d[j];
					min = m[i][k] + m[k+1][j] + d[i-1] * d[k] * d[j];
				m[i][j] = min;
			}
		}
	}
	return m[1][n];
}