$$ D(t,i)=\min_{1\leq j \leq n}D(t-1, j)+C(j,i)\\ \text{let }P(t, i):D(t,i)=D(t-1,P(t,i))+C(P(t,i),i) \\\rarr P(t,i)\leq P(t,i+1) $$

인 경우, t의 범위를 K라 할 때 분할 정복을 이용해 $D(t, 1\ldots N)$을 $O(KN\log N)$에 계산할 수 있다.

// l <= j <= r이고, D[t][s..e]를 구한다.
// D[t][m]을 구한 후, 남은 범위 양쪽에 대해 f를 호출
void f(int t, int s, int e, int l, int r) {
		if(s > e) return;
		int m = s + (e - s) / 2, opt = l;
		D[t][m] = 5571557155715571557;
		for(int j=l; j<=r; j++)
				if(D[t][m] > D[t-1][j] + C[j][m])
						opt = j, D[t][m] = D[t-1][j] + C[j][m];
		f(t, s, m-1, l, opt); f(t, m+1, e, opt, r);
}