Minimum path sum and triangle from the bottom

Why this matters

Many real choices are routes with a cost on each step. The cheapest road for a delivery, the route a robot can drive with the least energy, and the path through numbers with the smallest total all have this shape.

The previous lesson counted routes. This lesson keeps the same table idea, but each cell now holds a cost, and the table keeps the cheapest total instead of a count.

The second half teaches a trick that is worth keeping. A triangle of numbers can be solved from the bottom row upward. Then the table never needs more than one row at a time, and the answer ends up in one cell.

The grid: minimum path sum

Take a grid of numbers. Each number is the cost of stepping onto that cell. A route starts at the top-left cell and ends at the bottom-right cell, moving only right or down. The cost of a route is the sum of every cell it stands on, including the start and the end. The task is to find the smallest such sum. Programmers call this the minimum path sum.

Here is a small grid:

1 3 1
1 5 1
4 2 1

One route goes right, right, down, down. It stands on 1, 3, 1, 1 and 1, so its cost is 7. No other route is cheaper, and the table below shows that.

The recipe

The table is best[r][c], the cheapest cost to reach cell (r, c), including that cell's own cost. Follow the recipe from the tabulation lesson.

Definition: best[r][c] is the smallest total cost of any route from the start to cell (r, c).
Base case: best[0][0] is the value of the start cell, because the route is just that cell.
Recurrence: for any other cell, the route came from the cell above or the cell to the left. So best[r][c] equals the cell's own value plus the smaller of best[r - 1][c] and best[r][c - 1]. A neighbour that does not exist is left out of the comparison.
Loop order: row by row, left to right. Then both neighbours are filled before they are read.
Answer: best[rows - 1][cols - 1].

Worked example: the 3 by 3 grid

Fill the table one cell at a time. The top row has only a left neighbour, and the left column has only an upper neighbour.

Row 0. The start is 1. The next cell is 3 plus the left value 1, giving 4. The last cell is 1 plus 4, giving 5.

Row 1. The first cell is 1 plus the value above it, 1, giving 2. The centre is 5 plus the smaller of 4 (above) and 2 (left), giving 7. The last cell is 1 plus the smaller of 5 (above) and 7 (left), giving 6.

Row 2. The first cell is 4 plus the value above it, 2, giving 6. The middle cell is 2 plus the smaller of 7 (above) and 6 (left), giving 8. The last cell is 1 plus the smaller of 6 (above) and 8 (left), giving 7.

The table is:

 1  4  5
 2  7  6
 6  8  7

The bottom-right cell holds 7, which matches the route found earlier.

The triangle

A triangle of numbers has one number in its top row, two in the next row, three in the one after, and so on. Every number has two neighbours directly below it, one at the same column and one at the next column. A route starts at the top and moves down one row at a time, choosing one of those two neighbours at each step. It ends in the bottom row. The task is again to find the smallest total of the numbers on the route.

Here is a triangle with four rows:

The route 2, 3, 5, 1 costs 11. From 2 it steps to 3, which is in the cell below and to the left. From 3 it steps to 5, which is below and to the right. From 5 it steps to 1, which is below and to the left. That is one of many routes, and the minimum over all of them is the answer.

Give each number a row and a column. Row r has r + 1 numbers, and columns run from 0 to r. From the number at (r, c), the two choices in the next row are (r + 1, c) and (r + 1, c + 1).

Top-down: the table from the top

The first way to solve the triangle works from the top, the same way as the grid. Let best[r][c] be the smallest total from the top of the triangle to cell (r, c). A cell can be reached from the two cells above it, so:

best[r][c] equals the cell's value plus the smaller of the best values of the cells above it.

The top cell is the base case, and its best value is its own value. Filling the four rows gives:

row 0:      2
row 1:      5  6
row 2:     11 10 13
row 3:     15 11 18 16

The answer is the smallest number in the bottom row, 11. Note what this method needs. It must store the whole table, which holds 10 numbers for four rows. It must also scan the last row at the end to find the smallest value.

Bottom-up: start at the bottom

Now reverse the direction. Start at the bottom row. Its best values are the numbers themselves, because nothing lies below them.

Move up one row at a time. For each cell in the row above, its best value is its own number plus the smaller of the two best values directly below it. Those two values were already computed in the previous step.

Here is the bottom-up table for the same triangle. The first line is the bottom row, as it is at the start.

row 3:       4  1  8  3
row 2:      7  6 10
row 1:     9 10
row 0:    11

Work through the middle row. The first cell is 6 plus the smaller of 4 and 1, which is 7. The second cell is 5 plus the smaller of 1 and 8, which is 6. The third cell is 7 plus the smaller of 8 and 3, which is 10. The top row is 2 plus the smaller of 9 and 10, which is 11.

This method needs only one row at a time. Once row 2 is computed, row 3 is no longer needed. So a single list of numbers can serve as the table. The list starts as the bottom row, and each new row overwrites it. At the end, the list has one entry, and that entry is the answer.

A longer triangle

Here is a five-row triangle. Its bottom row is 4, 5, 2, 6, 5.

Each step up removes one entry from the list, so the list shrinks from five entries to one. Start with the bottom row. For the row above it, 2 7 4 4, each cell takes its own value plus the smaller of the two cells below:

2 + min(4, 5) = 6
7 + min(5, 2) = 9
4 + min(2, 6) = 6
4 + min(6, 5) = 9

The list becomes 6 9 6 9. The row 8 1 0 comes next, and it gives:

8 + min(6, 9) = 14
1 + min(9, 6) = 7
0 + min(6, 9) = 6

The list becomes 14 7 6. The row 3 8 gives 3 + min(14, 7) = 10 and 8 + min(7, 6) = 14, so the list becomes 10 14. The top cell gives 7 + min(10, 14) = 17.

The answer is 17, from the route 7, 3, 1, 4, 2. A check that tries all 16 routes through this triangle also finds 17. The bottom-up list never held more than five entries. A top-down table for the same triangle would hold 15 numbers.

Why the overwrite is safe

Suppose the list best holds the row below, and the code is computing row r. For column c, the code reads best[c] and best[c + 1]. Both still hold values from the row below, because the code has not reached them yet in this row. Then it writes the new value into best[c].

The next column reads best[c + 1] and best[c + 2]. The value at best[c + 1] is still the old one, so it is read correctly. Nothing is read after it has been changed. This is why the loop must go from left to right. Right to left would break this, as the mistakes section shows.

The program

The program below implements the grid table and the triangle, then tests them on several inputs. It uses std::min to compare two values.

C++ · editable

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

// Cheapest way from the top-left cell to the bottom-right cell,
// moving only right or down. Every cell holds a cost.
int min_path_sum(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<int>> best(rows, std::vector<int>(cols, 0));

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];
            } else if (r == 0) {
                best[r][c] = grid[r][c] + best[r][c - 1];
            } else if (c == 0) {
                best[r][c] = grid[r][c] + best[r - 1][c];
            } else {
                best[r][c] = grid[r][c] + std::min(best[r - 1][c], best[r][c - 1]);
            }
        }
    }
    return best[rows - 1][cols - 1];
}

// Smallest total from the top of the triangle to the bottom row.
// Each step moves to one of the two numbers directly below.
// Works from the bottom row upward, so only one row is kept.
int minimum_total(const std::vector<std::vector<int>>& triangle) {
    if (triangle.empty()) {
        throw std::invalid_argument("triangle is empty");
    }
    std::vector<int> best = triangle.back();
    for (int r = static_cast<int>(triangle.size()) - 2; r >= 0; --r) {
        for (int c = 0; c <= r; ++c) {
            best[c] = triangle[r][c] + std::min(best[c], best[c + 1]);
        }
    }
    return best[0];
}

// The greedy rule: from each cell, step to the smaller neighbour below.
int greedy_total(const std::vector<std::vector<int>>& triangle) {
    int total = triangle[0][0];
    int c = 0;
    for (int r = 1; r < static_cast<int>(triangle.size()); ++r) {
        if (triangle[r][c + 1] < triangle[r][c]) {
            ++c;
        }
        total += triangle[r][c];
    }
    return total;
}

int main() {
    std::vector<std::vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1},
    };
    std::vector<std::vector<int>> triangle = {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3},
    };
    std::vector<std::vector<int>> trap = {
        {1},
        {2, 3},
        {9, 9, 1},
    };
    std::vector<std::vector<int>> negatives = {
        {-1},
        {2, 3},
        {1, -1, -3},
    };

std::cout << "grid min path sum: " << min_path_sum(grid) << "\n";
    std::cout << "triangle minimum total: " << minimum_total(triangle) << "\n";
    std::cout << "trap triangle, bottom-up: " << minimum_total(trap) << "\n";
    std::cout << "trap triangle, greedy: " << greedy_total(trap) << "\n";
    std::cout << "negatives, bottom-up: " << minimum_total(negatives) << "\n";
    std::cout << "one row: " << minimum_total({{7}}) << "\n";
    return 0;
}

Output:

grid min path sum: 7
triangle minimum total: 11
trap triangle, bottom-up: 5
trap triangle, greedy: 12
negatives, bottom-up: -1
one row: 7

min_path_sum uses a full two-dimensional table, because it is the most direct reading of the recipe. The one-row version of the same pattern is in the previous lesson, and it works here in the same way.

minimum_total takes the bottom row as its starting list, then loops over rows from the second-last one to the top. The inner loop goes from c = 0 up to c = r, which covers all r + 1 cells of row r.

The empty-input check matters. Without it, triangle.back() would read past the start of an empty vector. The check throws an error with a clear message instead, and the caller can catch it.

The negative numbers need no special handling. The rule compares sums, and a sum can be negative just as well as positive. The route -1, 3, -3 costs -1, which is the smallest total.

A triangle with one row has no loop steps, so the answer is that one number.

Why the greedy rule fails

The greedy_total function takes the smaller neighbour at each step and never looks ahead. On most triangles it finds a good answer. The trap triangle shows where it goes wrong:

        1
       2 3
      9 9 1

From 1, the greedy rule sees 2 and 3 and picks 2, because it is smaller. From 2, it must go to 9 or 9, and it adds 9. The total is 1 + 2 + 9 = 12.

The route through 3 costs 1 + 3 + 1 = 5. The 3 looks worse at the first step, but it leads to a 1 below. Greedy cannot see that, because it decides each step without looking at the rows below. The bottom-up method checks both options at every level, so it finds 5.

Common mistakes

Off by one in the inner loop. Using c < r instead of c <= r leaves the last cell of each row unchanged. The stale value is then used in the next row up, and the answer is wrong without any error. The next program runs the bad version on the triangle from earlier, and it also shows the error message for reading past the end of a row.

C++ · editable

#include <algorithm>
#include <iostream>
#include <vector>

// Broken on purpose: the column loop stops one cell early.
int off_by_one(const std::vector<std::vector<int>>& triangle) {
    std::vector<int> best = triangle.back();
    for (int r = static_cast<int>(triangle.size()) - 2; r >= 0; --r) {
        for (int c = 0; c < r; ++c) {
            best[c] = triangle[r][c] + std::min(best[c], best[c + 1]);
        }
    }
    return best[0];
}

// Broken on purpose: keeps too few entries after each row, so the
// next row reads an entry that does not exist.
int reads_past_end(const std::vector<std::vector<int>>& triangle) {
    std::vector<int> best = triangle.back();
    for (int r = static_cast<int>(triangle.size()) - 2; r >= 0; --r) {
        for (int c = 0; c <= r; ++c) {
            best[c] = triangle[r][c] + std::min(best.at(c), best.at(c + 1));
        }
        best.resize(r);
    }
    return best[0];
}

int main() {
    std::vector<std::vector<int>> triangle = {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3},
    };
    std::cout << "off by one: " << off_by_one(triangle) << std::endl;
    std::cout << "reads past end: " << reads_past_end(triangle) << std::endl;
    return 0;
}

Output:

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

The first line is a wrong answer. The correct total is 11, and the program prints 9 with no warning. The second line is the error from at(), which checks the index and throws when it is out of range. After the row with three numbers is done, the list is cut to length 2. The next row needs index 2, which is past the end, so at() throws std::out_of_range. The message says that the index was 2 and the size was 2. The program then stops with exit code 134.

Choosing the smaller neighbour instead of computing both. The greedy function in the main program gives 12 on the trap triangle, where the correct answer is 5. Any rule that commits to a choice before looking at the rows below can make this mistake.

Starting the bottom-up loop from the wrong row. The loop must begin at the second-last row, triangle.size() - 2, because the bottom row is already in the list. Starting at triangle.size() - 1 makes the last column read best[c + 1] one past the end of the list, which is undefined behaviour with []. With at() it throws the same kind of std::out_of_range error shown above.

Reading the row without a size check. A triangle with no rows at all has no bottom row to start from. Check for it first, as the program does.

Practice

Exercise 1. Find the minimum path sum of this grid:

2 1
5 1

Show the answer

There are two routes. Going right then down costs 2 + 1 + 1 = 4. Going down then right costs 2 + 5 + 1 = 8. The minimum is 4.

Exercise 2. Find the minimum total of this triangle, using the bottom-up method. Write the list after each row.

    5
   4 9
  2 6 3

Show the answer

The bottom row is 2, 6, 3. The middle row becomes 4 + min(2, 6) = 6 and 9 + min(6, 3) = 12, so the list is 6, 12. The top row is 5 + min(6, 12) = 11. The answer is 11, from the route 5, 4, 2.

Exercise 3. Change minimum_total so that it finds the largest total instead of the smallest. Then use it on the four-row triangle from this lesson. What is the largest total?

Show the answer

Replace std::min with std::max in the inner loop. Nothing else changes. Running the changed version on the four-row triangle gives 21. That is the route 2, 4, 7, 8. Routes that start 2, 3 reach at most 18, and routes that start 2, 4 reach 21, so 21 is the largest.

Exercise 4. A triangle has n rows. Compare how many numbers the top-down table stores with how many the bottom-up list stores. Give both counts for 4 rows and for 1000 rows.

Show the answer

The top-down table has row 0 with 1 number, row 1 with 2, and so on up to row n - 1 with n numbers. The total is n(n + 1) / 2. For 4 rows, that is 10. For 1000 rows, it is 500500.

The bottom-up list holds one row at a time, so it stores n numbers. For 4 rows, that is 4. For 1000 rows, it is 1000.

Exercise 5. Predict the result if the inner loop of minimum_total runs from right to left, with for (int c = r; c >= 0; --c). Then check your prediction.

Show the answer

The prediction is that the answer changes, because the update order matters. Running this on the four-row triangle from the lesson gives 12, not 11. When column c is processed, best[c + 1] has already been replaced by the new value for this row, so the sum uses a value from the wrong row. Left to right is the only order that reads each entry before it changes.

Summary

A grid route cost table holds, in each cell, the cell's value plus the smaller of the cell above and the cell to its left.
A triangle can be solved top-down with a full table, or bottom-up with a single list that starts as the bottom row.
Bottom-up needs one row of storage, and its answer ends up in one entry.
The inner loop must run left to right, so each entry is read before it is overwritten.
Choosing the smaller neighbour at each step, without looking ahead, can give a worse total than the true minimum.

Minimum path sum and triangle from the bottom

Why this matters

The grid: minimum path sum

The recipe

Worked example: the 3 by 3 grid

The triangle

Top-down: the table from the top

Bottom-up: start at the bottom

A longer triangle

Why the overwrite is safe

The program

Why the greedy rule fails

Common mistakes

Practice

Summary

Stuck? Ask the tutor