Given a sequence of *n* words and the limit of the length of each line *M*, let the cost of putting *k* words with total *m* characters in a line be , design an O(*n* lg *n*) time algorithm to find the optimal way to break the sequence of words into lines with minimum cost.

**Solution**:

The solution is based on dynamic programming. Let *p*[*i*] be the total length for the first i words. Let *c*[*i*][*j*] be the cost of putting the *i*-th word to *j*-th word in the same line. By using the prefix sum of the length, each element of *c*[*i*][*j*] can be computed in constant time. Let *F*[*i*] be the optimal objective value for the subproblem containing the first *i* words. We get a recurrence relation *F*[*j*] = *F*[*i*] + *c*[*i*][*j*]. By using the recurrence relation, we get an O() time algorithm.

In order to speed up, note that *c*[*i*][*j*] satisfies quadrangle inequality, that is *c*[*i*][*k*] + *c*[*j*][*l*] ≤ *c*[*i*][*l*] + *c*[*j*][*k*] for all *i* ≤ *j* ≤ *k* ≤ *l*. Furthermore, let *d*[*i*][*j*] = *F*[*i*] + *c*[*i*][*j*], the problem becomes finding the minimum for each column of matrix *d*. Note that the matrix *d* also satisfies quadrangle inequality. We will use a queue = (), …, () to maintain the candidates, where and () is in the front of the queue. When processing to the *j*-th column, one element () in the queue means that in the submatrix *d*[1..*j*-2][*j*..*n*], row is the column minimum for columns to . Initially, the queue only contains (1, 1). When consider the column *j*, if *d*[*j*-1][*n*] is smaller then *d*[][*n*], then we need to dequeue until the *d*[][] < *d*[*j*-1][], where is the rear of the queue. Then, we find the smallest *h* > , such that *d*[][*h*] < *d*[*j*-1][*h*] and enqueue (*j*-1, *h*+1). Finding such *h* needs O(lg *n*) time by using binary search. Since each index can be enqueue and dequeue once, the total complexity is O(*n* lg *n*).

Note: This problem can be solved in linear time by using slope optimization.

**解法**：

解法是基於動態規劃。令*p*[*i*]為第一個字到第*i*個字的總長度。令*c*[*i*][*j*]為把第*i*個字到第*j*個字放到一行的費用。利用陣列*p*，每一個*c*[*i*][*j*]都可以在常數時間內計算出。令*F*[*i*]為前*i*個字的最佳解之花費，我們可得一遞迴關係式*F*[*j*] = *F*[*i*] + *c*[*i*][*j*]。 利用此遞迴關係，我們可得到O()時間的演算法。

有一個方法可以加速，因為*c*[*i*][*j*]滿足四邊形不等式，意即*c*[*i*][*k*] + *c*[*j*][*l*] ≤ *c*[*i*][*l*] + *c*[*j*][*k*]對所有的 *i* ≤ *j* ≤ *k* ≤ *l*。令*d*[*i*][*j*] = *F*[*i*] + *c*[*i*][*j*]，問題就變成是在矩陣*d*中找出每列的最小值。 此時矩陣*d*同樣也滿足四邊形不等式。我們可以利用一個queue (), …, ()來維護可能的最佳解範圍，其中且()是queue的頭。當處理到第*j*列時，queue中的元素()表示在子矩陣*d*[1..*j*-2][*j*..*n*]中，第行是第列到第列的最小值。一開始queue中只包含(1, 1)。當處理到第*j*列時，如果*d*[*j*-1][*n*]比*d*[][*n*]小，那麼我們必須把元素從queue中移除直到*d*[][] < *d*[*j*-1][]，是queue的尾。然後我們找出最小的*h* > ，使得*d*[][*h*] < *d*[*j*-1][*h*]，然後把(*j*-1, *h*+1) enqueue。利用二分搜尋可以在O(lg *n*)的時間內找到此*h*。因為每一個索引只能被enqueue和dequeue一次，所以總時間複雜度為O(*n* lg *n*)。

Reference: Zvi Galil and Kunsoo Park, “Dynamic programming with convexity, concavity and sparsity,” Theoretical Computer Science Volume 92, Issue 1, 6 January 1992, Pages 49–76.