Knuth's optimization

참고1 : https://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming

참고2 : http://codeforces.com/blog/entry/8219

Knuth's Optimization

---

다이나믹 프로그래밍 중에 다음과 같은 DP형태를 최적화 하는 방법입니다.

$$DP[i][j] = \underset {i<k<j}{min} (DP[i][k]+DP[k][j])+C[i][j]$$

이런 DP의 경우 $O(n^3)$만큼의 시간복잡도가 걸리게 되는데 이를 $O(n^2)$으로 최적화 하는 방법을 알아봅시다.

최적화를 위한 조건은 다음과 같습니다.

1) Quadrangle inequality

$$C[a][c]+C[b][d]\le C[a][d]+C[b][c]\;$$

$$where\; a\le b\le c\le d$$

2) Monotonicity

$$C[b][c] \le C[a][d]\; ,where\; a\le b\le c\le d$$

위 두 조건을 만족하는 경우에는 아래를 만족하게 됩니다.

$$A[i][j-1] \le A[i][j] \le A[i+1][j] $$

$$\quad where\ A[i][j]\ is\ the\ samllest\ k\ that$$

$$gives\ optimal\ answer\ of\ DP[i][k]+DP[k][j]+C[i][j]$$

A[i][j]의 최적해를 찾는 과정에서 k를 i+1부터 j-1까지 탐색하였지만, 위 식을 이용하게 되면 k를 탐색하는 범위가 줄게 됩니다.

(증명은 나중에 정리해보기로.. 3/24)

관련문제 : https://www.acmicpc.net/problem/11066

---

이번 글에서는 Knuth's Optimization에 관련된 내용에 대해 알아보았습니다.

질문이 있으시거나, 잘못된 내용을 발견하시면 댓글 남겨주시면 답변드리겠습니다.

감사합니다.