Dynamic Programming

• 표(table)을 만들어 채워가면서 답을 구하는 방법
• “programming”의 의미 : tabular method(표 방식)
• optimization problem을 해결하기 위해 쓰임

풀이 방법

1. 최적해의 구조적 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 상향식 방법으로 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.

Examples

Dynamic Programming 문제는 3가지 유형으로 나뉜다.
1. rod cutting
2. matrix-chain multiplication
3. longest common subsequence

1. rod cutting

11052번: 카드 구매하기

$n$인치 막대를 잘라서 판매하여 얻을 수 있는 최대 수익 $r_n$을 찾아라.

length $i$	1	2	3	4	5	6	7	8	9	10
price $p_i$	1	5	8	9	10	17	17	20	24	30

$r_n$은 $r_{n-1}, r_{n-2}, ..., r_1$로부터 구할 수 있다.
$r_n = max_{1<=i<=n}(p_i + r_{n-i})$
→ optimal substructure를 가졌다.

top-down

MEMOIZED-CUT-ROD(p, n)
	let r[0..n] be a new array
	for i = 0 to n
		r[i] = -∞
	return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
	if r[n] >= 0
		return r[n]
	if n == 0
		q = 0
	else q = -∞
		for i = 1 to n
			q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
	r[n] = q
	return q

bottom-up → function call이 없어서 top-down보다 효율적

BOTTOM-UP-CUT-ROD(p, n)
	let r[0..n] be a new array
	r[0] = 0
	for j = 1 to n
		q = -∞
		for i = 1 to j
			q = max(q, p[i] + r[j-i])
		r[j] = q
	return r[n]

시간 복잡도: $O(n^2)$

2. Matrix-chain multiplication

11049번: 행렬곱셈순서

$A_i$x…x$A_j$행렬을 optimal 순서로 곱했을 때의 연산 횟수 $m[i,j]$를 구하라.

matrix	$A_1$	$A_2$	$A_3$	$A_4$	$A_5$	$A_6$
demension	30×35	35×15	15×5	5×10	10×20	20×25

$p_k$는 $A_k$의 열의 개수 = $A_{k+1}$의 행의 개수 (단, $p_0$는 $A_1$의 행의 개수)
따라서 $A_k$의 크기는 $p_{k-1}$×$p_k$
$m[i,j] = \begin{cases}0& if\;i=j,\\\min_{i\le k<j}\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\}&if\;i<j.\end{cases}$
→ optimal substructure를 가지고 subproblem들이 overlap 되어있다.

MATRIX-CHAIN-ORDER(p)
	n = p.length - 1
	let m[1..n,1..n] be new table
	for i = 1 to n
		m[i,i] = 0 // 행렬이 1개일 때의 값 초기화
	for l = 2 to n // chain length
		for j = 1 to n-l+1
			j = i+l-1
			m[i,j] = ∞
			for k = i to j-1
				q = m[i,k] + m[k+1,j] + p_{i+1}p_{k}p_{j}
				if q < m[i,k]
					m[i,j] = q
	return m

시간복잡도: $O(n^3)$

3. Longest common subsequence (LCS)

9251번: LCS

$X_i$와 $Y_j$의 LCS의 길이 $c[i,j]$를 구하라.

subsequence $Z = <z_1, z_2, ..., z_k>$ of sequence $X=\;<x_1,x_2,...,x_m>$
단조 증가하는 X의 index sequence $<i_1,i_2,...,i_k>$
ex) X = <A, B, C, B, D, A, B>, Z = <B, C, D, B> ⇒ <2, 3, 5, 7>

$c[i,j] = \begin{cases}0&if\;i=0\;or\;j=0,\\c[i-1,j-1]+1&if\;i,j>0\;and\;x_i=y_j,\\max(c[i-1,j],c[i,j-1])&if\;i,j>0\;and\;x_i\neq y_j.\end{cases}$

LCS-LENGTH(X, Y)
	m = X.length
	n = Y.length
	let c[0..m,0..n] be new table
	for i = 1 to m // 초기화
		c[i,0] = 0
	for j = 0 to n
		c[0,j] = 0
	for i = 1 to n
		for j = 1 to n
			if x_i == y_j
				c[i,j] = c[i-1,j-1]+1
			elseif c[i-1,j] >= c[i,j-1]
				c[i,j] = c[i-1,j]
			else
				c[i,j] = c[i,j-1]
	return c

시간복잡도: $O(mn)$