Knuth Optimization

주어진 실수 $a_{i,j}(1 \le i \le j \le N)$에 대해 다음과 같이 정의된 $d_{i,j}$를 고려합니다.

$d_{i,j} = \begin{cases} a_{i.j} & \text{if } i=j \\ \min \left\{ k \in \{ i , i+1, \cdots , j-1 \} : d_{i,k} + d_{k+1,j} + a_{i,j}\right\} & \text{if } i<j\end{cases}$

이는 다음과 같은 $O(N^3)$짜리 동적계획법으로 해결할 수 있습니다.

for (int i=1;i<=N;i++){
    D[i][i] = a[i][i];
}

for (int l=1;i<N;i++){ // l: length of interval
    for (int i=1;i<=N-l;i++){
        int j = i+l;
        D[i][j] = INT_MAX;
        for (int k=i;k<j;k++){
            D[i][j] = min(D[i][j], D[i][k] + D[k+1][j] + a[i][j])
        }
    }
}

return D[1][N];

이것은 특정 조건을 만족하면 더 빠른 시간 안에 풀 수 있습니다. 위 코드에서 k의 검색 범위를 더 좁히는 방법이에요. 이를 위해서 $k_{i,j}$를 다음과 같이 정의합니다:

$k_{i,j} = \begin{cases} i & \text{if } i=j \\ k \in \{i, i+1 , \cdots j-1\} \text{ such that } d_{i,j} = d_{i,k} + d_{k+1,j} + a_{i,j} & \text{if } i < j\end{cases}$

이렇게 $d_{i,j}$를 결정할 때 사용된 $k$값(인덱스)을 계속 저장해나갈 때, $k_{i,j}$가 다음 조건을 만족하면 $\{ d_{i,j}\}$는 $O(N^2)$만에 계산 가능합니다.

$k_{i,j-1} \le k_{i,j} \le k_{i+1,j}$

for (int i=1;i<=N;i++){
    D[i][i] = a[i][i];
    K[i][i] = i;
}

for (int l=1;i<N;i++){ // l: length of interval
    for (int i=1;i<=N-l;i++){
        int j = i+l;
        D[i][j] = INT_MAX;
        for (int k=K[i][j-1];k<=min(K[i+1][j],j);k++){
            v = D[i][k] + D[k+1][j] + a[i][j];
            if (v < D[i][j]){
                D[i][j] = v;
                K[i][j] = k;
            }
        }
    }
}

return D[1][N];

배열 K를 만들어서 $k_{i,j}$를 저장했고, 세 번째 루프에서 $k$의 검색 범위를 더 줄였습니다. 이 코드가 $O(N^2)$임은 각 $l$에 대해 반복되는 연산이 많아야

$\begin{aligned} \sum _{i=1} ^{N-l} (k_{i+1,j} - k_{i,j-1} +1) &= \sum _{i=1} ^{N-l} (k_{i+1,i+l} - k_{i,i+l-1} +1) \\&= \sum _{i=2 } ^{N-l+1} k_{i,i+l-1} - \sum _{i=1 }^{N-l} k_{i,i+l-1} + N-l \\ &= k_{N-l+1,N} - k_{i,l} + N-l < 2N\end{aligned}$

이기 때문이에요. 이런 방식의 동적 계획법 최적화를 Knuth 최적화라고 합니다.