Skip to content
Tutorials Center
My learning

Topics

Lesson 164 of 225 ยท Dynamic Programming

Word Wrap, Box Stacking and Tile Stacking

Learn three DP problems in Python: optimal line breaking with the word wrap cost, box stacking as a 3D longest increasing chain, and bounded-run tile stacking.

This lesson collects three problems that look unrelated but each teaches a distinct DP skill. Word wrap shows how to turn a layout goal ("make the lines look even") into a cost and minimize it. Box stacking shows how to reduce a 3D puzzle to a chain problem you already know, the longest increasing subsequence. Tile stacking counts arrangements under a "no more than k in a row" rule, a pattern called a bounded run.

Word wrap (minimum raggedness)

Problem. You have a list of words and a line width W. Break the text into lines, keeping the word order, so that no line is longer than W. A line of length L costs (W - L)^2, except the last line, which is free. Minimize the total cost.

The squared cost punishes one very short line much more than two slightly short lines, so the result looks even, which is what text editors and typesetters try to do. A greedy approach (put as many words as fit on each line) is simple but not optimal.

The DP

Let cost[i] be the minimum cost of laying out words i..n-1 (the suffix starting at i). The next line holds words i..j-1 for some j, and the rest is a smaller instance of the same problem:

TEXT
cost[i] = min over j > i of  line_cost(i, j) + cost[j]
cost[n] = 0

where line_cost(i, j) is infinite if the words do not fit and 0 if j == n (last line). The length of words i..j-1 with single spaces is sum(len) + (j - i - 1). Store the best j for each i to rebuild the lines.

Python Word wrap with minimum cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two costs the program prints (46 for the DP, 52 for greedy). The DP never does worse than greedy and often does strictly better, because it will move a word down to the next line early to avoid a very ragged line later. The time is O(n * W / average word length) since the inner loop stops once the line is full; in the worst case it is O(n^2). Space is O(n).

A word longer than the width can never fit. In the code above the inner loop would break immediately, leaving cost[i] infinite, and the answer stays infinite. Real tools either split the word or let that one line overflow; decide on a rule before you code.

Box stacking

Problem. You have n types of boxes, each with a height h, width w and depth d. You have an unlimited supply of each type, and you may rotate a box so any of its three dimensions is the height. A box can sit on top of another only if its base is strictly smaller in both dimensions than the base of the box below. Find the tallest stack.

Reduce it to a chain problem

Each box type yields three orientations (choose which side is the height). Because we can place a box with the base turned either way, normalise every base so that base_width >= base_depth (swap if needed). Now "smaller in both dimensions" is a clean comparison of two numbers.

  1. Generate all orientations: 3 * n boxes.
  2. Sort them by base area descending (or by one dimension descending).
  3. Run a longest-chain DP: best[i] = height[i] + max(best[j]) over earlier boxes j whose base is strictly larger in both width and depth.
TEXT
best[i] = height[i] + max( best[j] for j < i if w[j] > w[i] and d[j] > d[i] )

The answer is the largest best[i]. It is the LIS recurrence with a weight (the height) and a two-dimensional comparison, much like weighted job scheduling.

Python Box stacking with the stack rebuilt

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the first input the best stack is 60 tall. The DP is O(n^2) over 3n boxes and uses O(n) space. The strictness matters: two boxes with the same base cannot be stacked, which is why the comparison uses > and not >=. If your version allows equal bases, change both comparisons.

Tile stacking (bounded runs)

Problem. You are building a wall of height n. Each course (row) is one tile, and you have m colours. No colour may appear in more than k consecutive courses. How many different walls are there?

Think of it as counting strings of length n over an alphabet of size m where no letter repeats more than k times in a row. The state needs to remember how long the current run is.

Let ends[i][r] be the number of valid walls of height i whose top run has length exactly r (1 <= r <= k):

  • A new run of length 1 starts with a different colour: ends[i][1] = (m - 1) * sum(ends[i-1][r] for all r).
  • A run is extended with the same colour: ends[i][r] = ends[i-1][r-1] for r >= 2.

For i = 1: ends[1][1] = m.

Python Counting walls with at most k equal tiles in a row

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With k = 1 no two neighbours match, so the count is m * (m-1)^(n-1): for (3, 2, 1) that is 2. The DP takes O(n * k) time and O(k) space. Real problems ask for the answer modulo a prime such as 1,000,000,007; apply % MOD after each multiplication and addition.

Text justification (greedy line packing)

Word wrap above minimizes raggedness. Text justification has a simpler goal: every line except the last must be exactly W characters wide, with extra spaces spread between words. A greedy pass is enough because the rules are fixed.

  1. Pack as many words as fit on a line, with at least one space between neighbours.
  2. For a normal line, split the leftover spaces as evenly as possible across the gaps. If they do not divide evenly, the leftmost gaps get one extra.
  3. A line with a single word, and the last line, are left-justified (padded on the right).
Python Full text justification

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each word is touched a constant number of times, so the time is O(total characters). The usual bugs are forgetting that a one-word line has zero gaps (division by zero) and justifying the last line.

Common mistakes

  • Charging the last line in word wrap. The final line is free; forgetting that pushes the optimizer to stretch it.
  • Using unsorted boxes. Without sorting by base, best[j] for an earlier j might not be final when you read it.
  • Allowing equal bases. The classic rule is strict; rotations of the same box with the same base would otherwise stack forever.
  • Mixing "at most k" with "exactly k". The state tracks the exact current run length, and the answer sums over all runs from 1 to k.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In word wrap, why is the last line not charged?

    A paragraph's final line is expected to be short, so charging it would make the optimizer distort the earlier lines.
  2. 2. Why does the squared cost (W - L)^2 make a better layout than the plain gap W - L?

    Squaring grows quickly, so the total is lowest when the slack is spread evenly across lines.
  3. 3. How many box orientations does the box stacking DP consider for n box types?

    Each box can have any of its three dimensions as the height, giving three orientations per type.
  4. 4. In the tile stacking DP, what does ends[i][r] store?

    The run length is the only extra information needed to enforce the 'at most k in a row' rule.

Summary

  • Word wrap: cost[i] = min over j of (W - len(i..j-1))^2 + cost[j], the last line costs 0; remember the best j to print the lines.
  • Greedy line filling is not optimal; the DP shifts words to avoid a very ragged line later.
  • Box stacking: create three orientations per box, sort by base area, then run a weighted LIS where the base must be strictly smaller in both dimensions; O(n^2).
  • Tile stacking: track the length of the current run; start a new run with (m - 1) choices or extend the run by one; O(n k).

Next: Stock Buy and Sell with k Transactions, a family of DPs with a small state machine.