수정 예정
knuth optimization은 아래 조건을 만족할 때 사용 가능합니다.
- 점화식 꼴 : DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j] (i < j < k)
- 사각 부등식(Quadrangle inequality) : C[a][c] + C[b][d] ≤ C[a][d] + C[b][c] (a ≤ b ≤ c ≤ d)
- 단조성(monotonicity) : C[b][c] ≤ C[a][d] (a ≤ b ≤ c ≤ d)
- 단, c(비용)은 k에 독립적
위 4가지 조건을 만족하면 아래 식이 성립합니다.
P[i][j] = DP[i][j]가 최소가 되기 위한 가장 작은 k일 때 P[i][j-1] ≤ P[i][j] ≤ P[i+1][j]
DP배열의 상태 공간은 N2개, 각각의 상태에 대해 해를 구할 때 O(N)이 걸리므로 총 O(N3)이 걸리는 문제를 knuth optimization를 사용하면 O(N2)에 해결할 수 있습니다.
연습 문제는 (이 링크)에 있습니다.