3장 Dynamic Programming

chap3. Dynamic programming(planning)

• 작은 문제가 반복되는 경우에 작은 문제를 계산하여 한번 계산한 값을 저장하고 검색 후 재사용하는 방식. = recomputing 대신 look up table 만들기.

fibonacci number

DP의 핵심 스텝

DP는 schedule을 사용하여 문제를 효율적으로 풀지만 메모리를 추가로 사용하고

divide and conquer는 문제를 blindly(무턱대고) 풀며, 스케줄링과 planning이 없다. - 겹치는 계산이 없을 때 쓰면 좋음.

Compute binomial coefficient=이항계수 문제

계속 이전 항끼리의 합을 구하는 방식이라 겹치는(over lapping)부분과 반복되는 계산이 많다.

basic operation = addition operation = B[r][c] = B [r-1][c-1] + B [r-1][c]

shortest path problem - Floyd’s algorithm

1. D(0) = 초기 값 graph를 만든 후,
2. D(1) = 1을 거쳐가는 경우를 모두 만들어 이전 dimension(D(0))의 값과 비교를 한다. 그렇게 해서 더 작은 걸 D(1)에 저장
3. D(2) = D(1)의 값과 2를 거쳐 가는 경우를 비교저장
4. D(3) = 3을 거치는
5. D(4) = 4를 거치는
6. 이러한 과정을 통해 모든 경로에 대한 가장 짧은 거리 table을 저장한다.

time complexity = T(n) = nxnxn = n^3

shortest 걸이를 저장하는 D(n) 외에도 경로를 저장하는 P(n)을 만들어 저장하면 어느 길을 통해 오는지 파악가능.

optimization 문제를 푸는 DP의 단계

optimal binary search Tree

각 node마다 probability를 부여하고 모든 노드에 대해

node에 가는 시간 x probability를 계산해 더한 값이 가장 작은 BST를 뜻함.

모든 BST경우를 구하는 데 걸리는 시간

DP를 사용하여 구하면

dimension을 넓혀가면서(i와 j의 차이를 넓혀가며) 표를 구해 저장하고, 마지막까지 계산하여 골에 도달하면 그 값이 BST값인 것.