Word Wrap

Medium · dynamic programming

A paragraph is made of words, and the list lengths gives the number of letters in each word, in order. You must lay the words out on lines that are width characters wide.

The words keep their order, and every word goes on exactly one line.
Words on the same line are separated by exactly one space. A line with words of lengths a, b and c is a + b + c + 2 characters long, and that must not be more than width.
A line's spare is width minus its length: the unused space at its end.

Every line except the last costs spare * spare. The last line is free, however much room it leaves.

Return the smallest total cost over all valid ways to lay out the words.

Every word fits on a line by itself. If all the words fit on one line, that line is the last one and the answer is 0.

Examples

Example 1

Input: lengths = [3, 2, 2, 5], width = 6

Output: 10

Put the 3 alone (spare 3, cost 9), the two 2s together (length 5, spare 1, cost 1), and the 5 alone on the free last line. The total is 10. Packing 3 and 2 first looks tighter but leaves the second 2 alone with spare 4, which costs 16.

Example 2

Input: lengths = [5, 5, 5], width = 10

Output: 50

Two words need 11 characters, which is too many, so each word has its own line. The first two lines each have spare 5 (cost 25 each) and the last is free.

Example 3

Input: lengths = [4], width = 10

Output: 0

A single line is the last line, and the last line is free.

Constraints

1 <= len(lengths) <= 500
1 <= width <= 1000
1 <= lengths[i] <= width