AL - DP

💡

• 작은 문제를 먼저 해결한다.
• 결과를 저장한다.
  • 다시 계산하지말고 저장된 결과를 가져온다.
• Bottom-Up

Recursive Property를 세운다. (fn = fn-1 + fn-2)

작은 문제부터 해결해가며 bottom-up 방식으로 문제를 해결한다.

Binomial Coefficient (이항 계수)

//Recursive
int bin(int n, int. k){
	if(n==k)
		return 1;
	else
		return bin(n-1,k)+bin(n-1,k-1);
}

→DP 사용해서 해결 가능하다.

• Recursive Property
  • $B[i][j] = B[i-1][k] + B[i-1][k-1]; 0<j<i$
  • $B[i][j]= 1 ;(j=0, j=i)$

//DP
int bin2(int n, int k){
	index i,k;
	int B[0..n][0..k];
	for (i=0;i<=n;i++){
		for(j=0;j<=min(i,k);j++){
			if(j==0 | i==j)
				return 1;
			else
				B[i][j] = B[i-1][k] + B[i-1][k-1];
		}
	}
	return B[n][k];
}

• Time Complexity : $\theta(nk)$

Floyd’s Algorithm for Shortest Paths

• G= (V,E) weighted directed graph(acyclic - 사이클 없다.)에서 그래프상의 각 정점에서 정점까지의 최단거리를 구한다.

• 모든 최단거리 문제는 정점 i에서 j까지 거리를 저장하는 $D(i,j)$를 구하는 것이 목표.

• $D^{(k)}[i][j]$ : vi에서 vj까지 {v1,v2..vk}를 거쳐서가는 최단거리.

• $D^{(0)}[i][j] = W[i][j]$ 이고 구하고자 하는 건 $D^{(n)}[i][j]$

• Recursive Property

  • $v_k$를 지나지 않을 때 : $D^{(k)}[i][j] = D^{(k-1)}[i][j]$
  • $v_k$를 지날 때: $D^k[i][j] = D^{k-1}[i][k] + D^{k-1}[k][j]$

void floyd (int n, const number W[][], number D[][]){
	index i,j,k;
	D = W;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				D[i][j] = min(D[i][j],D[i][k]+D[k][j]);
}

→ $T(n)=n^3$

• $P[i][j]$ : i에서 j의 최단거리에서 거쳐가는 점 중 가장 높은 index를 저장한다. 없다면 0 저장.

void folyd2(int n, const number W[][], number D[][], index P[][]){
	index i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			P[i][j]=0;
	D=W;

	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(D[i][k]+D[k][j]<D[i][j]){
					D[i][j]= D[i][k] + D[k][j];
					P[i][j]= k;
				}
}

// 정점에서 다른 정정으로 가는 최단거리 사이에 있는 정점 출력
void path (index q, r){
	if(P[q][r]!=0){
		path(q,P[q][r]);
		cout<<"v"<<P[q][r];
		path(P[q][r],r);
	}
} 

Optimization Problems

Principle of Optimality

: Instance에 대한 Optimal Solution은 그것을 이루는 Subinstances의 solution도 Optimal하다.

→ DP 사용하기 위한 조건

Optimal Binary Search Tree

• BST : node 당 key 하나, 왼쪽 subtree는 작거나 같은 key, 오른쪽 subtree는 크거나 같은 key
• Optimal BST : key를 찾는 평균 시간을 최소화한다.

struct nodetype{
	keytype key;
	nodetype* left;
	nodetype* right;
};

typedef nodetype* node_pointer;

void search(node_pointer tree, keytype keyin, node_pointer &p){
	bool found;
	p=tree;
	found=false;
	
	while(!found){
		if(p->key == keyin)
			found = true;
		else if (keyin < p->key)
			p = p->left; // 왼쪽 child로 이동
		else
			p = p->right; // 오른쪽 child로 이동
	}
}

• 주어진 key 찾는 시간 : depth(key) +1

• $K_1, K_2...K_n$ 인 n개의 키가 순서대로 존재

• $p_i$ : $K_i$가 찾는 값일 확률

• $c_i$ : $K_i$를 찾기 위한 비교 횟수

⇒ $\sum_{i=1}^n c_ip_i$ 를 최소화 한다.

• $K_i$ 부터 $K_j$ 까지 정렬된 tree는 $\sum_{m=i}^jc_mp_m$을 최소화하는데 이를 Optimal 이라한다.

• $A[i][j]$ :

  • $A[i][i] = p_i$

• Principle of Optimality

  • OBST의 모든 subtree가 optimal
  • 모순에 의해 증명된다.

$A[1][k-1] + (p_1+...+p_{k-1}) + p_k +A[k+1][n] + (p_{k+1}+...p_n)$

• $A[1][k-1]$ : left subtree
• $A[k+1][n]$ : right subtree
• $(p_1+..+p_{k-1})$ , $(p_{k+1}+...+p_n)$: root와 비교하는 시간
• $p_k$ : average time

∴ $A[1][n] = \min_{1\le k \le n}(A[1][k-1] + A[k+1][n]) + \sum_{m=1}^np_m$

($A[1][0] = A[n+1][n] = 0$)

일반화

$A[i][j] = \min_{i\le k \le j}(A[i][k-1] + A[k+1][j]) + \sum_{m=i}^jp_m ; i<j$

$A[i][i] = p_i$

$A[i][i-1] = A[j+1][j] = 0$

void optsearchtree(int n ,const float p[], float& minavg, index R[][]){
	index i,j,k,diagonal;
	float A[1..n+1][0..n];
	for(i=1; i<=n; i++){
		A[i][i-1]=0;
		A[i][i]= P[i];
		R[i][i]=i;
		R[i][i-1]=0;
	}
	A[n+1][n]=0;
	R[n+1][n]=0;
	for(diagoanl=1; diagonal<=n-1; diagonal++)
		for(i=1; i<=n-diagonal;i++){
			j=i+diagonal;
			A[i][j] = min(A[i][k-1]+A[k+1][j]) + sum(p_m);
			R[i][j] = k // minimum 만드는 k
		}
	minavg= A[1][n];
)

//Build OBST
node_pointer tree(index i,j){
	index x;
	node_pointer p;
	k= R[i][j];
	if(k==0)
		return NULL;
	else{
		p = new nodetype;
		p->key = Key[k];
		p->left = tree(i,k-1);
		p->right = tree(k+1, j);
		return p;
	}
}

Traveling Salesperson Problem

• v1에서 시작해서 모든 정점을 돌고 돌아오는 최단거리 경로를 찾는다

• 모든 가능한 경우의 수 : $(n-1)!$

• $W$ : weight,
  $D[v_i][A]$: $v_i$ 에서 시작해 A에 속한 각 정점을 한 번씩만 사용해 v_1으로 가는 최단 경로 길이

• 구하고자 하는 값 : $D[v_1][V-\{v_1\}]$

• Recursive Property

  • $D[v_i][A] = \min_{v_j∈A}(W[i][j]+D[v_j][A-\{v_j\}])$, $A\ne 0$
  • $D[v_i][0] = W[i][1]$

void travel(int n, const number W[], index P[][], number& minlength){
	index i,j,k;
	nubmer D[1..n][subset of V-{v1}];
	
	for(i=2; i<=n; i++){
		D[i][0] = W[i][1];
		for(k=1;k<=n-2;k++)
			for(all subsets A ⊆ V-{v_1} containig k vertices)
				for(i such that. i!=1 and v_i is not in A){
					D[i][A] = min(W[i][j]+D[i][A-{v_j}]);
					P[i][A] = j; // minimum 만드는 j
				}
		D[1][V-{v_1}] = min(W[1][j]+D[1][V-{v_1,v_j}]);
		P[1][V-{v_1}] = j // minimum 만드는 j
		minlength = D[1][V-{v_i}];
	}
}

• $T(n) = \theta(n^22^n)$