15-4 Printing neatly

Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of $n$ words of lengths $l_1, l_2, \ldots, l_n$, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of $M$ characters each. Our criterion of "neatness" is as follows. If a given line contains words $i$ through $j$, where $i \le j$ , and we leave exactly one space between words, the number of extra space characters at the end of the line is $M - j + i - \sum_{k = i}^j l_k$, which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of $n$ words neatly on a printer. Analyze the running time and space requirements of your algorithm.

First observe that the problem exhibits optimal substructure in the following way: Suppose we know that an optimal solution has $k$ words on the first line. Then we must solve the subproblem of printing neatly words $l_{k + 1}, \dots, l_n$. We build a table of optimal solutions solutions to solve the problem using dynamic programming. If $n − 1 + \sum_{k = 1}^n l_k < M$ then put all words on a single line for an optimal solution. In the following algorithm $\text{PRINT-NEATLY}(n)$, $C[k]$ contains the cost of printing neatly words $l_k$ through $l_n$. We can determine the cost of an optimal solution upon termination by examining $C[1]$. The entry $P[k]$ contains the position of the last word which should appear on the first line of the optimal solution of words $l_k, \dots, l_n$. Thus, to obtain the optimal way to place the words, we make $l_{P[1]}$ the last word on the first line, $l_{P[P[1]]}$ the last word on the second line, and so on.

PRINT-NEATLY(n)
    let P[1..n] and C[1..n] be new tables
    for k = n downto 1
        if sum_{i = k}^n l_i + n - k < M
            C[k] = 0
        q = ∞
        for j = 1 to n - k
            cost = sum_{m = 1}^j l_{k + m} + m - 1
            if cost < M and (M - cost)^3 + C[k + m + 1] < q
                q = (M - cost)^3 + C[k + m + 1]
                P[k] = k + j
        C[k] = q