Yeah it’s tricky. One way of recovering the line breaks is to have another array of words.size() called “lineBreaks”. lineBreaks[i] = for a line ending with the ith word, what is the index of the optimal line break (the index of the word in words that starts a new line that ends with the ith word).

For a lot of these path recovery things (like shortest path or other DP), you need to leave “breadcrumbs” / clues when you find the optimal solution for a subproblem. So that means you should be setting lineBreaks whenever you set the memo[] with a new optimal value.

Then when everything has run, you start by looking at lineBreaks of words.size() - 1. For the book example, this will be 6. Now look 1 less than 6 (the next line will end with the word at index 5), lineBreaks[5] = 2 or 3 (2 or 3 since they give the same messiness whether c is on first line or on second line, depends on your algo implementation). Say its 3. Then we need to look at lineBreaks[2] = 0. 0 is obviously the first line break to start everything, so the path is 0, 3, 6.