Dynamic Programming

Dynamic Programming In mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps - wikipedia

Algorithms Review Backtracking Greedy Algorithm Dynamic Programming search every possible solution optimal guaranteed inefficient Greedy Algorithm find the best at each stage – MST not always optimal needs a proof Dynamic Programming efficient recursive algorithm

Recursive Algorithm Divide-and-Conquor Dynamic Programming top-down solution Fibonnaci can be inefficient duplicated computations Dynamic Programming bottom-up recursive and solve above limitations Fibonacci calculate F(1), F(2), .... and store the results use them to calculate F(n) F(n) = F(n-1) + F(n-2) = {F(n-2)+F(n-3)} + {F(n-3)+F(n-4)} = [{F(n-3)+F(n-4)}+{F(n-4)+F(n-5)}] +[{F(n-4)+F(n-5)}+{F(n-5)+F(n-6)}] = ...

Binomial Coefficient Redundancy ! n k n - 1 k - 1 n - 1 k = + int bino(int n, int k) { if (k==0 || n==k) return 1; else return bino(n-1, k-1) + bino(n-1, k); } {bino(n-2, k-2) + bino(n-2, k-1)} + {bino(n-2, k-1) + bino(n-2, k)} Redundancy !

Binomial Coefficient (2) kC0 = kCk = 1 2C1 = 1C0 + 1C1 3C1 = 2C0 + 2C1 3C2 = 2C1 + 2C2 4C1 = 3C0 + 3C1 4C2 = 3C1 + 3C2 ... ... ... ... 1 2 3 4 6 bino(int n, int k) { long bc[n][k]; for( int i=0; i<=n; i++) for( int j=0; j<=min(i,k); j++ ) if( j==0 || j==i ) bc[i][j]=1; else bc[i][j] = bc[i-1][j-1] + bc[i-1][j]; return bc[n][k]; }

Floyd’s Algorithm find all pairs shortest paths Floyd Alg. apply Dijkstra alg. for each vertex inefficient Floyd Alg. number each vertex from 1 to n start from W(0)=W, ends with W(n) which is a set of shortest paths – bottom up compute W(k) from W(k-1) - recursion typical dynamic programming problem

Floyd’s Algorithm W(k)[i][j] Adjacent Matrix: W shortest path from vi to vj the path traverses vertices among {v1, v2, ... , vk} 1 v1 v2 9 3 5 1 3 v5 v4 2 v3 3 4

Floyd’s Algorithm W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j]) shortest path from vi to vj using {v1, v2, … , vk} Case 1: the path does not visit vk Ex) W(5)[1][3] = W(4)[1][3] = 3 Case 2: the path visits vk Ex) W(2)[5][3] = W(1)[5][2] + W(1)[2][3] = 4+3 = 7 Case 1 Case 2

플로이드 알고리즘 <4> 데이터 구조 초기화 인접배열

플로이드 알고리즘 <5> 재귀 관계식 계산 W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j])

String Matching Edit Distance number of any following costs to make two strings match subs – match insertion deletion after any above operation, you are given shorter strings to match

delete remaining tail of t the characters match or substitute to make them match – i-1 and j-1 insert a char to s – append the last char of t to s, so compare s with t[0:n-1] delete a char from s – s is shorter, t is the same

Algorithm Review The number of function call grows exponentially The maximum number of distinct function call is Let’s make a table like .... the number of unique function calls is |s| * |t|

cell[i, j] means cost to make two strings match s[0..i] and t[0..j] worst case: subs all chars – diagonal values are i computing a cell requires three cells

엘리베이터 최적화 <1> 엘리베이터 최적화 문제 소개 엘리베이터가 멈추는 횟수는 k번으로 제한되어 있다고 가정. 계단을 올라가는 것과 내려가는 것 사이에 차이가 없다고 가정. 걸어 올라가거나 내려가는 사람 수가 같은 층이 여러 명 존재할 경우 가장 낮은 층에 세운다. 반드시 탑승객이 내리겠다고 한 위치에서만 서는 것은 아니다. 예) 27층과 29층에서 내리는 탑승객이 있을 경우 28층에서 멈출 수 있음. 문제의 목적은 걸어서 올라가거나 내려가야 하는 사람 수를 최소화할 수 있는 층에 멈추는 것이다. 이때, 사람 수를 최소화한다는 것은 걷는 비용의 최소화를 의미한다.

엘리베이터 최적화 <2> 동적 프로그래밍을 이용한 해결 방법 f2층 f1층 동적 프로그래밍은 재귀 알고리즘을 바탕으로 함을 생각하자. k번째 멈출 층을 결정하는 것은 k-1번째 멈추는 모든 가능한 풀이의 비용에 따라 결정할 수 있다. 우선, f1층에서 선 후에 f2층에서 서는 경우를 생각해 보자. 이때, f2층은 목적지가 f1층 이하인 탑승객과는 상관이 없다. 즉, 문제를 두 조각으로 나눌 수 있다. 이 부분에서 동적 프로그래밍을 사용할 수 있음을 알 수 있다. f2층에서 내릴 탑승객은 f1층 위의 탑승객들만 관계되어 있다. 물론 f1층과 f2층 사이의 탑승객들은 f1층 f2층 중에서 한 곳에 내릴 것이다. f2층 f1층

엘리베이터 최적화 <3> mi,j i층 까지, j번 멈추면서 모든 승객을 운반하기 위한 최소 비용을 mi,j으로 정의한다. 그렇다면, (j+1)번째 멈출 위치는 이전에 i층에서 j번째로 멈추는 층보다 높으며, 이것은 i층보다 위로 올라갈 사람에게만 유효하다. 즉, 어느 층이 더 가까운지를 바탕으로 새로 멈추게 될 층과 i층에서 내릴 승객 으로 나눠야 한다. j+1번째 stop! ?층 i층 k층 j번 이동

엘리베이터 최적화 <3> mi,j=min{k=0…i-1}{mk,j-1 - walk(k,∞)+walk(k,i)+walk(i,∞)} 마지막으로 (j번째) 멈춘 층이 i층이었다면, 그 전에 (j-1번째) 멈췄던 층은 i층보다 작은 어떤 k층이었다. 그렇다면, mi,j은 mk,j-1로부터 k층 위로 올라가는 모든 승객에 대한 비용(walk(k,∞)) 을 빼고, i층에 멈추는 비용(walk(k,i)+walk(i,∞))을 더하면 된다. 이 문제를 해결하는데 있어 가장 중요한 것은 a층에서 멈춘 다음 b층에서 멈출 때, 승객들이 걸어서 이동한 층수의 총합을 계산하는 walk(a,b) 함수이다. walk(i,∞) walk(k,∞) j번째 stop! i층 k층 walk(k,i) j-1번 이동

Similar Problems A numerical sequence is monotonically increasing if the ith element is at least as big as the (i − 1)st element. The maximum monotone subsequence problem seeks to delete the fewest number of elements from an input string S to leave a monotonically increasing subsequence. Thus a longest increasing subsequence of “243517698” is “23568.” Find the longest sequence of elephants whose weights are increasing but whose IQ’s are decreasing. Can this be done as a special case of edit distance?