Comment by svalorzen

I'm not sure I understand why dynamic programming wouldn't work (and the author explicitly mentioned Knuth). Tex's main job is literally doing line breaks, which is the exact same problem being tackled here. I would expect a similar approach (progressively build a graph of the most promising breaking points) to be effective. Why wouldn't it be the case here?