Consider the problem of neatly printing a paragraph of text on a printer with fixed-width fonts. The input text is a sequence of n words containing L1,...,Ln, characters, respectively. Each line on the printer can hold up to M characters (Assume that L1,...,Ln are all less than or equal to M). If a printed line contains words i through j , then the number of blanks left at the end of the line (given that there is one blank between each pair of words) is M-j+i-(Li+...+Lj). We wish to minimize the sum, over all lines except the last, of square of the number of blanks at the end of each line. Give an efficient dynamic programming algorithm to compute this value.
For example:
M = 10
input text: I hate exam
output text:
I hate
exam
minimize sum of square of the number of blanks at the end of each line = 4