Chap 3. Dynamic Programming

 - Merge sort를 접근하는 데 있어 Divide and Conquer는 적절하다, recursive도 맞을 수 있지만 overlapping이 문제가 되기에 bottom up으로 올라가는 게 맞을 수 있다

- XX로 시작되지 않는 문자열 나열하기는 Qk = 2Qk-1(Y~,Z~) + 2Qk-2(XY~, XZ~)

- Binomial coefficient 조합값 찾기 nCk = n-1Ck-1 + n-1Ck

 

- Floyd's Algorithm은 AFSP(All Fair Shortest Path) 찾기 문제이다. 

- 기본적인 접근법은 Dynamic Programming, 핵심 아이디어는 K를 거치느냐 안거치느냐

- Dk[i,j] (i~j로 가는 경로 중 k 이하 node를 거치는 경로) 를 다음과 같은 경우의 수로 나눈다

- K를 거치는 경우 <Dk-1[i,k] + Dk-1[k,j]>, 거치지 않는 경우 <Dk-1[i,j]> 이 둘 중 최소값을 찾으면 된다

- 실제 프로그래밍에서는 k를 따로 3차원 배열로 만들 필요가 없음(K는 이전 k값을 보고 계속 덮어 씌우면 됨)

- 모든 문제를 DP로 해결할 수 있는 것은 아니다, Principle of Optimality 가 있어야한다(최단 경로의 sub 경로도 최단)

 

- Chained Matrix Multiplication 문제, 행렬간의 곱셈을 할 때 어떻게 해야 곱셈을 최소화 할 수 있을까

- 기본적으로 M1(p*q) X M2(q*r) 을 진행하면 p*q*r 의 곱셈수가 발생

- 따라서 최소화하기 위해서는 DP를 활용해서 한다

- M[i,j] = M[i,k] + M[k+1,j] + d(i-1)d(k)d(j) 의 공식을 통해 구체화해나가는데 풀어나가는 방향은 대각선

 

- Traveling SalePerson 문제 

- 그래프의 모든 노드를 한 번만 방문하는데, 최단경로를 구하는 문제(오일러 사이클)

- D[V1,{Vertex}] = v1 버텍스로부터 시작해서 Vertex를 한번씩 최단경로로 방문

- D[V1,{V2, V3, V4}] = min(W(1,j)+ D[j,A-{Vj}]) 의 공식을 통해 Dynamic programming