In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is
here), the official solution given in Instructor's Manual to Accompany Introduction to Algorithms, Second Edition, is an algorithm that minimizes the extra spaces at the ends of lines cubed.
My question is: why cubed? Why not squared? Or some other power?
Best Answer
If you used first powers, it would have no selectivity as the total number of spaces at the ends of lines is just the length of a line times the number of lines minus the length of the text. As you increase the power, you penalize large gaps at the end of the line more. It is really a question of taste. Would you rather have gaps of $10,1,1,1,1,1,1$ or $0,8,0,0,8,0,0?$ Cubes will pick the second and squares the first.