Knuth’s Optimization Link to heading

1. Introduction Link to heading

Knuth’s Optimization은 최적 이진트리 문제(optimal binary tree problems)에 적용하는 특별한 Optimization 이다.
시간복잡도(time complexity)을(를) \(O(N^3)\)에서 \(O(N^2)\)로 줄인다.
다음의 Conditions 들을 만족해야 활용가능하다.

반복되는 구조가 다음의 케이스 일 때 활용 가능
\[dp[i][j] = \min_{i < k < j}{dp[i][k] + dp[k][j]} + C[i][j]\]
적용가능성의 충분 조건은
\[A[i][j - 1] \le A[i][j] \le A[i + 1][j]\]
Where,
- \(A[i][j]\)은(는) 최적의 답을 주는 가장 작은 k
- \[dp[i][j] = dp[i - 1][k] + C[k][j]\]
- \(C[i][j]\)는 주어진 cost function
가장 중요한 것은 Knuth’s Optimization은 \(C[i][j]\)이 다음의 두 조건을 만족해야 활용 가능
- Quadrangle inequality (사각 부등식)
  - \[C[a][c] + C[b][d] \le C[a][d] + C[b][c], a \le b \le c \le d\]
- Monotonicity (단조성)
  - \[C[b][c] \le C[a][d], a \le b \le c \le d\]