The problem of accurate formatting?

Question

Programming

In one programming textbook, the task is given: a text of n words of length l _i , a line of width M. It is necessary to format the text in such a way as to minimize the sum of cubes of free residuals of the width on all lines except the last one (formally, print k _j : indexes of the last word of each line ). An instruction is given to use the methods of dynamic programming.
I can not allocate a substructure in the decision in any way. I would be grateful if someone could point me in the right direction.

Answer 1

I can’t say anything about the substructure, but this is a simplified Knuth-Plass algorithm about paragraph alignment, so the direction of thought is to see their work :) From the wiki:

Formally, the algorithm defines a value called badness associated with each possible line break; the badness is increased if the spaces on the line must stretch or shrink too much to make the line the correct width. Penalties are added if a breakpoint is particularly undesirable: for example, if a word must be hyphenated, if two lines in a row are hyphenated, or if a very loose line is immediately followed by a very tight line. The algorithm will then find the breakpoints that will minimize the sum of squares of the badness (including penalties) of the resulting lines. If the paragraph contains n possible breakpoints, the number of situations that must be evaluated naively is 2n. However, by using the method of dynamic programming, the complexity of the algorithm can be brought down to O(n2) (see Big O notation). Further simplifications (for example, not testing extremely unlikely breakpoints such as a hyphenation in the first word of a paragraph) lead to an efficient algorithm whose running time is almost always of order n. A similar algorithm is used to determine the best way to break paragraphs across two pages, in order to avoid widows or orphans (lines that appear alone on a page while the rest of the paragraph is on the following or preceding page). However, in general, a thesis by Michael Plass shows how the page breaking problem can be NP-complete because of the added complication of placing figures.[18] A similar algorithm is used to determine the best way to break paragraphs across two pages, in order to avoid widows or orphans (lines that appear alone on a page while the rest of the paragraph is on the following or preceding page). However, in general, a thesis by Michael Plass shows how the page breaking problem can be NP-complete because of the added complication of placing figures.[18] A similar algorithm is used to determine the best way to break paragraphs across two pages, in order to avoid widows or orphans (lines that appear alone on a page while the rest of the paragraph is on the following or preceding page). However, in general, a thesis by Michael Plass shows how the page breaking problem can be NP-complete because of the added complication of placing figures.[18]