Reconstructing the answer by storing choices

Why this matters

A dynamic programming table can give you a number: the lowest cost, the most points, the fewest moves. Often that number is not what the user needs. A text editor that wraps a paragraph needs the line breaks, not only the cost of the layout. A route planner needs the route, not only its length.

This lesson shows how to get the full answer from a table. The method is simple. When you fill a cell, store the choice that produced its value. When you finish, start at the final cell and follow the stored choices back to the start. The steps you followed are the answer.

The earlier lessons in this module showed how to fill the table and how to compute a best value. This lesson assumes you can already do that. It focuses on what to store and how to walk back.

Words you will need

• Cell: one entry of a table. In C++ a table is often a std::vector of values, and a cell is one element.
• Choice: the earlier cell that gave the best value for the current cell. A choice is stored as an index or a letter.
• Walk back: follow the stored choices from the final cell toward the start. Each step moves to the cell named by the stored choice. Walking back gives the answer in reverse, so the result often needs reversing.
• Path: a sequence of cells, one after another, from the start to the end.
• Infinity sentinel: a very large number used to mean "not reachable". The program needs a special value because a cell may have no valid way to be reached.
• Structured binding: a C++17 feature that unpacks a pair or a struct into named variables. For example, const auto& [row, col] = cell; names the two parts of cell.
• Line: in the word wrap example, a row of text on the page.
• Cost: a number that measures how bad a choice is. Lower is better.

The idea: one note per cell

Look at a DP table that stores only values. The final cell tells you the best total. To find the path, you would have to recompute which earlier cell was best at each step. That is extra work, and it is easy to get wrong.

The fix is to write down the answer to "which earlier cell did I come from?" at the moment you compute each cell. The note is cheap. It is one number or one letter for each cell. When the table is done, the notes form a chain. Start at the final cell, read its note, move to that cell, read its note, and continue until you reach the start.

Two parts make up the method:

1. Fill the table. Store the best value and the choice in each cell.
2. Walk back. Start at the final cell and follow the choices. Collect the pieces, then reverse the list if the walk went backward.

A small example by hand: wrapping go on now

Word wrap means putting words on lines so that each line is no longer than a fixed width. Use this rule for cost. A line that is not the last one costs the square of the empty space left at its end. The last line costs 0, because it does not need to be full. A line may not be longer than the width.

Take three words, go, on and now, and a width of 6. The table has four cells, numbered 0 to 3. Cell j holds the best cost for laying out the first j words. Cell 0 is 0, because no words need no lines.

To fill cell j, try every line that could end with word j - 1. Each line starts at some word i. The cost is the best value at cell i plus the cost of the line from word i to word j - 1. Keep the smallest total, and store the i that gave it as the choice.

Cell 1 holds the first word only. The line go is 2 characters, so the empty space is 4. The cost is 4 times 4, which is 16. Since go is the only option, the best value is 16 and the choice is 0.

Cell 2 holds go on. There are two options. One line holds only on, with empty space 4, which costs 16. Adding the best value of cell 1 gives 32. The other line holds go on, which is 5 characters, so the empty space is 1 and the cost is 1. Adding the best value of cell 0 gives 1. The smaller value is 1, so the best value is 1 and the choice is 0.

Cell 3 holds all three words, and it is the last cell. Its line is the final line, so it costs 0 whatever its length. One option is the line now alone. Its cost is 0, and it adds to cell 2, whose best value is 1. The total is 1. Another option is the line on now, which is 6 characters. Its cost is 0, but it adds to cell 1, whose best value is 16. The total is 16, which is worse. The best value is 1, and the choice is 2, which means the last line starts at word 2.

Now walk back from cell 3. Its choice is 2, so the last line is word 2, which is now. Move to cell 2. Its choice is 0, so the line before is words 0 and 1, which is go on. Move to cell 0, which is the start. The lines, in reverse order, are now and then go on. Reversing them gives go on followed by now.

The program below does this for any list of words. Running it on this input gives the same result:

6
go on now

The output is:

[go on]
[now]
lines: 2, cost: 1

Program 1: word wrap with stored choices

The program reads the width from the first line of input. It reads the words from the rest of the input, split on spaces. It prints each line and the total cost. The cost function and the rule for the last line are the same as in the example above.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
 
// Lays out words in lines of at most `width` characters.
// A line that is not the last costs (width - length) * (width - length). The last line costs 0.
// Returns false when some word is longer than the width.
bool wrap_words(const std::vector<std::string>& words, int width,
                long long& total_cost, std::vector<std::string>& lines) {
    const std::size_t n = words.size();
    const long long inf = std::numeric_limits<long long>::max() / 4;
    std::vector<long long> best(n + 1, inf);    // best[j]: lowest cost for the first j words
    std::vector<std::size_t> choice(n + 1, 0);  // choice[j]: the word where the last line starts
    best[0] = 0;
 
    for (std::size_t j = 1; j <= n; ++j) {
        int len = 0;
        // Try every line that ends with word j - 1. Move the start i left one word at a time.
        for (std::size_t i = j; i-- > 0;) {
            if (i + 1 < j) len += 1;  // the space between word i and word i + 1
            len += static_cast<int>(words[i].size());
            if (len > width) break;   // a longer line will not fit either
            const long long gap = width - len;
            const long long cost = (j == n) ? 0 : gap * gap;
            if (best[i] < inf && best[i] + cost < best[j]) {
                best[j] = best[i] + cost;
                choice[j] = i;
            }
        }
    }
 
    if (best[n] >= inf) return false;
    total_cost = best[n];
 
    // Walk back from the end, following the stored choices.
    lines.clear();
    for (std::size_t j = n; j > 0; j = choice[j]) {
        std::string line;
        for (std::size_t k = choice[j]; k < j; ++k) {
            if (k > choice[j]) line += ' ';
            line += words[k];
        }
        lines.push_back(line);
    }
    std::reverse(lines.begin(), lines.end());
    return true;
}
 
int main() {
    int width = 0;
    std::cin >> width;
    std::vector<std::string> words;
    std::string w;
    while (std::cin >> w) words.push_back(w);
 
    long long cost = 0;
    std::vector<std::string> lines;
    if (!wrap_words(words, width, cost, lines)) {
        std::cout << "no layout: a word is longer than the width\n";
        return 0;
    }
    for (const std::string& line : lines) {
        std::cout << "[" << line << "]\n";
    }
    std::cout << "lines: " << lines.size() << ", cost: " << cost << '\n';
}

Compile it with g++ -std=c++20 -Wall -o wrap wrap.cpp. The loop in the walk back runs while j is greater than 0. Each step moves j to choice[j], which is always smaller than j, so the loop must end.

Example 2: when the greedy rule loses

A common first idea for word wrap is greedy. Put as many words on each line as fit, then start a new line. Greedy is fast and often close. It can still be worse than the table, and the table can show exactly where it loses.

Take the words dddd, a, a, eeeee and eeeee, with width 10. The greedy rule puts dddd a a on the first line, because that is 8 characters and the next word would make it 14. The gap is 2, so the cost is 4. The second line holds eeeee alone, because adding the next eeeee would make 11 characters. Its gap is 5, so the cost is 25. The last line costs 0. The total is 29.

The table finds a better layout. It puts dddd a on the first line, with a gap of 4 and a cost of 16. It puts a eeeee on the second line, with a gap of 3 and a cost of 9. The last line eeeee costs 0. The total is 25.

The program gives the same answer:

10
dddd a a eeeee eeeee

The output is:

[dddd a]
[a eeeee]
[eeeee]
lines: 3, cost: 25

The lesson is not that greedy is wrong. It is that a choice made for the current line can hurt the lines after it. A table that compares all choices at each cell cannot make that mistake, and the stored choices show which layout it picked.

Example 3: a path through a grid

The next problem has two dimensions. A robot stands at the top-left corner of a grid of numbers. It can move one step right or one step down. Each cell it enters adds its number to a running total. The task is to find the path to the bottom-right corner with the largest total, and print that path.

The table has one cell for each grid position. Cell (r, c) stores the largest total of any path from the top-left to that position. To fill it, look at the cell above and the cell to the left. Take the larger of the two totals, add the number in this cell, and store it. The choice is a letter: D if the best path came from above, and R if it came from the left.

The walk back starts at the bottom-right corner. Read its letter. If the letter is D, move up one row. If it is R, move left one column. Stop when you reach the top-left corner. The positions you visited, reversed, form the path.

Take this grid:

3 3
5 3 2
1 9 1
4 2 8

The first number is the number of rows and the second is the number of columns. The bottom-right corner, (2, 2), holds 8 and has a best total of 27. Its choice is R, so the best path came from the cell to its left, (2, 1). That cell has the choice D, so it came from (1, 1). Cell (1, 1) has the choice D, so it came from (0, 1). Cell (0, 1) has the choice R, so it came from (0, 0), the start. Reversing these steps gives the path (0, 0), (0, 1), (1, 1), (2, 1) and (2, 2), with the sum 5 + 3 + 9 + 2 + 8 = 27.

Here is the program. It prints the best sum, then the cells on the path with their values.

#include <algorithm>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
 
int main() {
    int rows = 0;
    int cols = 0;
    std::cin >> rows >> cols;
    std::vector<std::vector<int>> grid(rows, std::vector<int>(cols));
    for (auto& row : grid) {
        for (int& value : row) std::cin >> value;
    }
 
    // best[r][c]: the largest sum of a path from (0, 0) to (r, c) that moves only right or down.
    // from[r][c]: 'D' if that path arrives from above, 'R' if it arrives from the left.
    const long long none = std::numeric_limits<long long>::min();
    std::vector<std::vector<long long>> best(rows, std::vector<long long>(cols, none));
    std::vector<std::vector<char>> from(rows, std::vector<char>(cols, '.'));
 
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (r == 0 && c == 0) {
                best[r][c] = grid[r][c];
                continue;
            }
            const long long above = (r > 0) ? best[r - 1][c] : none;
            const long long left = (c > 0) ? best[r][c - 1] : none;
            if (above >= left) {
                best[r][c] = grid[r][c] + above;
                from[r][c] = 'D';
            } else {
                best[r][c] = grid[r][c] + left;
                from[r][c] = 'R';
            }
        }
    }
 
    // Walk back from the bottom-right corner to (0, 0), following the stored choices.
    std::vector<std::pair<int, int>> path;
    int r = rows - 1;
    int c = cols - 1;
    while (true) {
        path.emplace_back(r, c);
        if (r == 0 && c == 0) break;
        if (from[r][c] == 'D') {
            --r;
        } else {
            --c;
        }
    }
    std::reverse(path.begin(), path.end());
 
    std::cout << "best sum: " << best[rows - 1][cols - 1] << '\n';
    std::cout << "path:";
    for (const auto& [row, col] : path) {
        std::cout << " (" << row << ',' << col << ")=" << grid[row][col];
    }
    std::cout << '\n';
}

The output for the grid above is:

best sum: 27
path: (0,0)=5 (0,1)=3 (1,1)=9 (2,1)=2 (2,2)=8

A second grid, 2 rows by 3 columns, shows the same method on a smaller case. Its input is 1 2 3 on the first row and 4 5 6 on the second. The output is:

best sum: 16
path: (0,0)=1 (1,0)=4 (1,1)=5 (1,2)=6

Here the best path goes down first, because the cell below 1 holds 4, which is larger than the 2 to its right.

The grid version stores one letter per cell instead of a full coordinate. This works because the previous cell is always either directly above or directly to the left. The letter says which one, and the coordinates follow from it.

Common mistakes

Storing only the values. A table with the best values but no choices can give the number and nothing else. To print the path, you would have to recompute each step. Store the choice in the same loop where you store the value. The two belong together.

Walking past the start. The walk must stop at the start cell. In the word wrap program the walk stops when j reaches 0. In the grid program it stops at (0, 0). Without a stop, the walk reads a cell that does not exist. A std::vector read with .at() then fails with a real error. This program stored a choice that pointed one past the end of a 5-element vector:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

The program stops with exit code 134. The fix is to make sure every stored choice is a valid index, and that the walk stops at the start.

Printing in the wrong order. The walk visits the last piece first, so the list it builds is backward. Both programs call reverse before printing. Forgetting this prints the lines in reverse. The output still looks plausible, so the mistake is easy to miss. Check the first and last lines of your output against the input.

Mixing up the stored index. In the word wrap table, choice[j] is the start of the last line that ends before word j. The walk uses it as the start of a line. If you store the end of the line instead, the walk produces lines that overlap or skip words. Write the meaning of each stored value in a comment next to the array.

Ties. Two layouts can have the same total cost. The program keeps the first one it finds, because the test uses < and not <=. Changing that test changes which layout is printed, but not its cost. If the problem asks for one specific answer, say which tie rule you use.

Practice

Exercise 1. Run the word wrap by hand for the words go on now with width 5. Give the lines and the total cost.

Show the answer

The lines are go on and now. The line go on is 5 characters, so its gap is 0 and its cost is 0. The last line costs 0. The total cost is 0. The program prints the same two lines and cost: 0.

Exercise 2. A word wrap table for 5 words stores choice[5] = 3 and choice[3] = 0. Which words are on each line, in order from top to bottom?

Show the answer

The walk starts at cell 5 and goes to cell 3. The last line holds words 3 and 4, which are the fourth and fifth words, counting from 0. It then goes from cell 3 to cell 0. The line before holds words 0, 1 and 2. In order from top to bottom, the lines are words 0 to 2, then words 3 and 4.

Exercise 3. For the grid path (0,0), (0,1), (1,1), (2,1), (2,2), write the moves as a string of R and D, one letter per step.

Show the answer

The steps are right, down, down, right. The string is RDDR. Each letter is the move from one cell to the next, which is the same information the stored choices give during the walk back.

Exercise 4. Suppose the grid program did not store the letter in from, and instead tried every neighbour again during the walk back. Why does storing the letter avoid that work, and what does it cost in memory?

Show the answer

Storing the letter means the walk back reads one cell and moves once. Trying both neighbours again would need a comparison at every step, and the comparison must repeat the same tie rule. The letter costs one char per cell, which is one byte per cell in the program. For a 1,000 by 1,000 grid, that is about 1 MB, and the table of totals is about 8 MB, since each long long is 8 bytes.

Exercise 5. The word wrap function returns false when some word is longer than the width. Why does it check best[n] >= inf before the walk back, and what would go wrong if the walk ran anyway?

Show the answer

When a word is too long, no line can hold it, so the cells that depend on it never get a value. Their stored value stays at the sentinel, and their choice stays at 0. The walk back would then print all the words as one long line, and the cost printed would be the huge sentinel number. The check stops the program before the walk starts.

Summary

• A DP table gives a best value. To get the path or the chosen pieces, store a choice in each cell as you fill it.
• The choice is the earlier cell that produced the best value. It can be an index in a one-dimensional table or a letter such as D or R in a grid.
• Walk back from the final cell by following the stored choices until you reach the start, then reverse the collected pieces.
• A greedy rule can lose to the table. The table compares every choice at each cell, so the stored choices show its real decisions.
• Check that the walk stops at the start and that every stored choice is a valid index.