Printing Neatly - Problem Statement

Given $n$ words with lengths $l_i$ and line width $W$. find the lowest sum of (trailing space)^3 for all lines except the last. $dp[i]$ = min cost to arrange words $i$ to $n$.

Transition: $dp[i] = \min_{j > i} (dp[j] + cost(i, j-1))$ where $cost$ is cube of spaces. The cube cost penalizes uneven lines heavily. QI can be shown to hold for this cost. Apply D&C improvement: $O(n \log n)$ instead of $O(n^2)$. This is it behind TeX's line breaking.