Knuth Optimization - Dynamic Programming

Knuth Optimization은 Dynamic Programming에서 점화식이 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다.

조건 1) DP 점화식 꼴

$D[i][j] = \min_{i < k < j}(D[i][k] + D[k][j]) + C[i][j]$

조건 2) Quadrangle Inequalty (사각부등식)

$C[a][c] + C[b][d] \leq C[a][d] + C[b][c], a \leq b \leq c \leq d$

조건 3) Monotonicity (단조성)

$C[b][c] \leq C[a][d], a \leq b \leq c \leq d$

조건 2와 조건 3을 만족하면 $A[i][j]$ = $D[i][j]$가 최소가 되기 위한 가장 작은 $k$라고 했을 때 아래 식을 만족한다.

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

이와 관련된 증명은 여기에 기술되어 있다.

위 부등식을 통해 원래 $O(N^3)$으로 해결되는 것이 $O(N^2)$에 해결된다.

예시 문제로 2015년 인터넷 예선 F번 문제를 생각해보자.

F번 문제에서 DP 점화식은 다음과 같다.

$D[i][j] = \min_{i \leq k < j}(D[i][k] + D[k+1][j]) + C[i][j]$

조건 1의 점화식 꼴을 맞춰주기 위해 새로운 DP 배열 $E[i][j] = D[i+1][j]$을 정의하자.

$E$의 점화식은 아래와 같다.

$E[i][j] = \min_{i < k < j}(E[i][k]+E[k][j]) + C[i+1][j]$

여기서 $C[i][j]$는 i번째 수와 $j$번째 수 사이에 있는 수의 합이므로 위의 조건 2와 조건 3을 만족한다.

위 세 가지 조건을 모두 만족하므로 이 문제는 Knuth Optimization을 통해 최적화를 할 수 있다.

아래는 인터넷 예선 F번 문제를 $O(N^2)$ 시간에 해결하는 코드다.

#include <bits/stdc++.h> using namespace std; int T, N; int A[503], S[503]; int D[503][503], K[503][503]; int main() { for (scanf("%d", &T);T--;){ scanf("%d", &N); for (int i=1;i<=N;i++) scanf("%d", A+i), S[i] = S[i-1] + A[i]; for (int i=1;i<=N;i++) D[i-1][i] = 0, K[i-1][i] = i; for (int d=2;d<=N;d++){ // d = j-i for (int i=0;i+d<=N;i++){ int j = i+d; D[i][j] = 2e9; for (int k=K[i][j-1];k<=K[i+1][j];k++){ int v = D[i][k] + D[k][j] + S[j] - S[i]; if (D[i][j] > v) D[i][j] = v, K[i][j] = k; } } } printf("%d\n", D[0][N]); } }