Can we solve the "printing neatly" problem using a greedy algorithm rather than dynamic programming?

The "printing neatly" problem in the "introductions to algorithms" book is solved via dynamic programming. It's Problem 5.3 and the solution is found here

I think this problem could be simply solved by a greedy algorithm. Just put as many words per line as possible intil you 开发者_C百科can't fit the next word and so move to a new line.

Can someone help me understand if this solution is enough ? (the greedy algo)

Here's the problem: Printing neatly

Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1,l2,...,ln, 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 and we leave exactly one space between words, the number of extra space characters at the end of the line is the difference between M and the total number of characters in the words plus the spaces between them .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.

No, because as is often the case with greedy algorithms, short sighted decisions now (deciding how many words for the current line) end up forcing higher cost later. For example, suppose we can have 10 chars per line.

Greedy solution

xx xxx xx    cost = 1
xxxxx        cost = 125
xxxxx        cost = 0 (last line)

Better solution

xx xxx       cost = 64
xx xxxxx     cost = 8
xxxxx        cost = 0 (last line)

The greedy solution packs more words onto the first line, but that actually produces a higher total solution cost.