All Problems
Hard Problemsminimizationlinearpartition

Word Wrap Problem

Given a sequence of word lengths and a fixed line width, arrange the words into lines, keeping their order, so each line's total length stays within the width, minimizing a penalty based on the leftover space on every line but the last.

Do this lesson first: coin change

Example input

8 words of lengths 7, 1, 5, 3, 3, 5, 3, 7 into lines of width 10

Expected output

28

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 0, the empty prefix, laid out for free. Fill left to right, because every j the recurrence reads is strictly smaller than i. cost(j, i) is the squared leftover space on a line holding words j through i - 1, counting one space between neighbours, or infinity if they do not fit. The one exception is the final cell: the last line of the whole text is not penalized, so cost(j, n) is 0 for every j whose words fit. That exception is what makes the last cell drop below its neighbour instead of climbing past it.

i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
0
9
1
18
2
27
3
28
28
word-wrap.ts
  1. 1function wordWrap(words, width) {
  2. 2 const n = words.length;
  3. 3 const dp = [0];
  4. 4 for (let i = 1; i <= n; i++) {
  5. 5 dp[i] = Infinity;
  6. 6 let used = -1;
  7. 7 for (let j = i - 1; j >= 0; j--) {
  8. 8 used += words[j] + 1;
  9. 9 if (used > width) break;
  10. 10 const slack = width - used;
  11. 11 const cost = i === n ? 0 : slack * slack;
  12. 12 dp[i] = Math.min(dp[i], dp[j] + cost);
  13. 13 }
  14. 14 }
  15. 15 return dp[n];
  16. 16}
Base caseComputedBeing readAnswer

The code, the trap, the variations

word-wrap.ts
  1. 1function wordWrap(words, width) {
  2. 2 const n = words.length;
  3. 3 const dp = [0];
  4. 4 for (let i = 1; i <= n; i++) {
  5. 5 dp[i] = Infinity;
  6. 6 let used = -1;
  7. 7 for (let j = i - 1; j >= 0; j--) {
  8. 8 used += words[j] + 1;
  9. 9 if (used > width) break;
  10. 10 const slack = width - used;
  11. 11 const cost = i === n ? 0 : slack * slack;
  12. 12 dp[i] = Math.min(dp[i], dp[j] + cost);
  13. 13 }
  14. 14 }
  15. 15 return dp[n];
  16. 16}

Where people go wrong

Filling each line as full as it will go. It feels obviously right and it is wrong, because a line that fits one more word cheaply now can force a nearly empty line later, and the penalty is squared, so one badly stranded word outweighs several slightly loose lines. On these 8 words greedy pays 52 against an optimum of 28, and the entire difference is one line holding a single 3. The second trap is forgetting that the last line is free. Penalizing it is a different problem with a different answer, and the recurrence looks identical, so the mistake survives every test you would think to write.

  • Penalize the leftover space itself rather than its square.

    The recurrence does not change at all, but the answer does, and greedy becomes optimal. Summing the raw leftovers counts the same total wasted space no matter where the breaks go, apart from the last line, so nothing is gained by being clever. The squaring is the entire reason this needs a table.

  • Penalize the last line like every other line.

    Delete the i === n case. That is the version most sources present, and it is worth filling in both to see how much the single free line moves the answer.

  • Words may be hyphenated across lines.

    A word no longer belongs to exactly one line, so an index into the word list stops naming the state. You need the break position inside a word too, and the table gains a dimension.

Palindromic Substring CountOptimal Strategy for a Game