Minimum path sum and triangle from the bottom in Python

Why this matters

Many problems ask for the cheapest route instead of the number of routes. A delivery driver wants the shortest total distance. A network packet wants the route with the least delay. A game character wants the path that collects the fewest penalty points. Each cell or road has a cost, and the total cost of a route is the sum of the costs it touches.

This lesson takes the grid idea from the unique paths lesson and changes the question. Instead of counting routes, it finds the smallest total. Then it moves to a triangle of numbers, where the shape is different. The triangle case teaches a trick that makes the table smaller: work from the bottom row up. Each row then needs only the row directly below it, so the program can keep a single list.

Every program in this lesson is a plain Python file. The programs marked python run print their output without reading input. To run one on your own computer, save it as main.py and run python3 main.py. The outputs shown were produced on Python 3.14.

Part 1: Minimum path sum in a grid

The problem

Here is a grid of costs. The robot starts at the top-left cell and must reach the bottom-right cell. It may move only right or down. The cost of a route is the sum of the numbers in every cell it enters, including the start and the end.

1 3 1
1 5 1
4 2 1

Two routes show the idea. The route right, right, down, down visits 1, 3, 1, 1, 1 and costs 7. The route down, down, right, right visits 1, 1, 4, 2, 1 and costs 9. The cheapest route is the first one, and its cost is 7.

A plain search would try every route. A 20 by 20 grid has far too many routes for that. Dynamic programming finds the answer by working out the cheapest cost to reach each cell, and then reusing those answers.

Step 1: Define the table

Let dp[i][j] mean the smallest total cost of any route from the top-left cell to cell (i, j). The total includes the cost of cell (i, j) itself. The answer we want is dp[-1][-1], the value at the bottom-right cell.

The table is built from the smaller answers to the cells before it in the walk. The robot arrives at cell (i, j) from above or from the left. So the cheapest way to reach (i, j) is the cheaper of the two cheapest ways to reach those neighbours, plus the cost of (i, j) itself.

Step 2: Fill the table by hand

Start with the top-left cell. Its cost is 1, so dp is 1 there.

The top row has no cell above it, so each cell can only be reached from the left. Its dp value is its own cost plus the value to its left: 1, then 1 + 3 = 4, then 4 + 1 = 5.

The left column has no cell to its left, so each cell can only be reached from above: 1, then 1 + 1 = 2, then 2 + 4 = 6.

The middle cells take the cheaper of the two neighbours:

• Cell (1, 1) has cost 5. Its neighbours are dp[0][1] = 4 above and dp[1][0] = 2 to the left. The cheaper is 2, so dp = 5 + 2 = 7.
• Cell (1, 2) has cost 1. Its neighbours are dp[0][2] = 5 above and dp[1][1] = 7 to the left. The cheaper is 5, so dp = 1 + 5 = 6.
• Cell (2, 1) has cost 2. Its neighbours are dp[1][1] = 7 above and dp[2][0] = 6 to the left. The cheaper is 6, so dp = 2 + 6 = 8.
• Cell (2, 2) has cost 1. Its neighbours are dp[1][2] = 6 above and dp[2][1] = 8 to the left. The cheaper is 6, so dp = 1 + 6 = 7.

The finished table is:

1 4 5
2 7 6
6 8 7

The bottom-right cell holds 7, which is the answer.

Step 3: The program

The program below fills the table with a list of lists and checks the edges with if tests. It also has a version that keeps one row, which is covered in the next step. The function min returns the smaller of the values it is given.

Output:

2D table:
[1, 4, 5]
[2, 7, 6]
[6, 8, 7]
answer = 7
rolling answer = 7

The printed table matches the hand-filled table above. The branches for the top row and the left column handle the edges, so the program never reads a cell that is outside the grid. Without them, the program would read a value from the wrong place with no error. The mistakes section shows this.

Step 4: Keep one row

Each cell reads only the cell above it and the cell to its left. So, as in the unique paths lesson, one row of numbers is enough. The list starts with the values of the row above. Then it is updated one cell at a time, from left to right.

Before a cell in dp[j] is overwritten, it still holds the value from the row above. That is the "from above" value. The cell dp[j - 1] has already been overwritten for this row, so it holds the "from left" value. Going left to right is what makes both values correct at the same moment.

Walk through the example with one list named dp:

• After the first row of costs, dp is [1, 4, 5].
• Second row, costs 1 5 1. For j = 0, the cell is on the left column, so only the value from above counts: 1 + 1 = 2. For j = 1, the cell costs 5, and the cheaper of dp[1] = 4 from above and dp[0] = 2 from the left is 2, so 5 + 2 = 7. For j = 2, the cell costs 1, and the cheaper of dp[2] = 5 from above and dp[1] = 7 from the left is 5, so 1 + 5 = 6. Now dp is [2, 7, 6].
• Third row, costs 4 2 1. The same rule gives [6, 8, 7].

The last value is dp[2], which is 7. The program prints 7 for both versions.

A second example: why the cheapest neighbour is not enough

A tempting shortcut is to always step to the cheaper neighbour. That fails on the same grid. From the top-left cell, the right neighbour costs 3 and the down neighbour costs 1, so the shortcut moves down. From there, the right neighbour costs 5 and the down neighbour costs 4, so it moves down again to cost 4. Then it moves right to cost 2, and right again to cost 1. The total is 1 + 1 + 4 + 2 + 1 = 9. The true cheapest route costs 7.

The mistake is that the shortcut looks only one step ahead. The table looks at every route into each cell, so it never throws away a route that could turn out cheaper later.

Part 2: The triangle

The shape

A triangle has rows. Row 0 has one number, row 1 has two numbers, row 2 has three, and so on. Each number has a position (r, c), where r is the row and c is the position within the row, both counted from 0.

From position (r, c), a step goes to one of the two numbers directly below it: (r + 1, c) or (r + 1, c + 1). The walk starts at the single top number and ends on any number in the bottom row.

Here is an example. The walk is 2, then 3, then 5, then 1. Check each step: 3 is below 2 on the left, 5 is below 3 on the right, and 1 is below 5 on the left. Its total is 2 + 3 + 5 + 1 = 11.

    2
   3 4
  6 5 7
 4 1 8 3

The goal is to find the walk with the smallest total. Unlike the grid, there is no single end cell. The walk may end in any position of the bottom row.

In Python, the triangle is a list of lists. Row 0 is [2], row 1 is [3, 4], and so on. The list for row r has r + 1 values, so len(triangle[r]) is the length of that row.

Why top-down is awkward

The grid approach works from the top-left corner outward. Each cell's best total depends on the cells above it. For a triangle, that is possible, but two things make it clumsy.

First, a middle cell can be reached from two different cells above it. You must compare two options each time, as in the grid.

Second, the answer can be any cell in the bottom row. After filling the table, you must scan the whole bottom row and take the smallest value. The table needs one full list for every row of the triangle, so it has about as many numbers as the triangle itself.

The bottom-up idea

Turn the question around. Ask: for each cell, what is the smallest total from this cell down to the bottom? The answer for a cell is its own number plus the smaller of the two answers directly below it. Both of those answers come from the row below, which is the only row that matters at that point.

The bottom row is the starting point. Its answers are just its own numbers, because no steps remain. Then we move up one row at a time. Each new row uses only the row beneath it, and the result is a single number at the top, which is the answer.

Work the example. The bottom row is 4 1 8 3, so best starts as [4, 1, 8, 3]. Here best[c] means the smallest total from the cell at position c in the current row down to the bottom.

• Row 2 is 6 5 7. For c = 0, the cell is 6, and the two options below are best[0] = 4 and best[1] = 1. The smaller is 1, so best[0] = 6 + 1 = 7. For c = 1, the cell is 5, and the options are best[1] = 1 and best[2] = 8. The smaller is 1, so best[1] = 5 + 1 = 6. For c = 2, the cell is 7, and the options are best[2] = 8 and best[3] = 3. The smaller is 3, so best[2] = 7 + 3 = 10. Now best is [7, 6, 10].
• Row 1 is 3 4. For c = 0, the options are best[0] = 7 and best[1] = 6. The smaller is 6, so best[0] = 3 + 6 = 9. For c = 1, the options are best[1] = 6 and best[2] = 10. The smaller is 6, so best[1] = 4 + 6 = 10. Now best is [9, 10].
• Row 0 is 2. The options are best[0] = 9 and best[1] = 10. The smaller is 9, so best[0] = 2 + 9 = 11.

The answer is best[0] = 11. Only one list was used. It is reused for every row, and only its first entries change as the program moves up.

Why one list works

The program updates best[c] from left to right. When it updates best[c], it reads best[c] and best[c + 1]. Both still hold the values from the row below, because best[c] is replaced only after it is read, and best[c + 1] is not reached until the next step. The program below also contains a top-down version for comparison. It runs both methods on 200 random triangles and checks that the answers match.

The slice best[:len(row)] in the trace line makes a new list of the first entries only. The trace shows the values for the current row and leaves out the unused entries at the end. The random.Random(42) line creates a random number generator with a fixed seed, so the run repeats the same numbers each time.

Output:

2D table:
[1, 4, 5]
[2, 7, 6]
[6, 8, 7]
answer = 7
rolling answer = 7
row 2: [7, 6, 10]
row 1: [9, 10]
row 0: [11]
bottom-up answer = 11
top-down answer = 11
agreed on 200 random triangles: 200
largest triangle had rows: 50

The three row lines match the hand trace. The random numbers are between -99 and 99. The count of 200 means both methods gave the same answer on every triangle. The largest row count depends on the seed, so it may differ on another Python version.

Common mistakes

1. Walking the row from right to left

The update reads best[c + 1], and that value must still be from the row below. Walking right to left breaks this, because best[c + 1] was already replaced by the current row. Here is the wrong version:

Output:

row 2: [10, 6, 10]
row 1: [13, 10]
row 0: [12]
buggy answer = 12

The correct answer is 11, and the program prints 12. The bug gives a plausible number and no error. The fix is to walk left to right, as in the main program.

2. Using the wrong loop bound

The inner loop must stop at the length of the current row, not the length of the bottom row. The bottom row is longer, so this version reads past the end of the current row:

def min_total_wrong_bound(triangle):
    best = list(triangle[-1])
    for r in range(len(triangle) - 2, -1, -1):
        row = triangle[r]
        for c in range(len(best)):
            best[c] = row[c] + min(best[c], best[c + 1])
    return best[0]
 
 
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3],
]
print("answer =", min_total_wrong_bound(triangle))

Output. The folder part of each path is shown as /path/to. An IndexError is Python's error for reading a list position that does not exist:

Traceback (most recent call last):
  File "/path/to/main.py", line 16, in <module>
    print("answer =", min_total_wrong_bound(triangle))
                      ~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^
  File "/path/to/main.py", line 6, in min_total_wrong_bound
    best[c] = row[c] + min(best[c], best[c + 1])
              ~~~^^^
IndexError: list index out of range

The path in the first line of each entry depends on where you saved the file. The rest of the output is what Python prints for this code. The first row above the bottom has three cells, so row[3] is outside the list. Python does not print the index or the length here, unlike Java. Instead, the line that failed is shown, and the ^^^ marks point at the part of that line that failed, which is row[c]. The fix is to loop to len(row), as the main program does.

3. Forgetting the edge cells in a grid

In the grid table, the top row and the left column have only one neighbour each. Reading dp[i - 1][j] when i is 0 reads dp[-1][j], which is the bottom row, not an error. Python does not stop there, so the program gives a wrong number:

Output:

answer without edge checks = 3

The correct answer is 7. The wrapped reads return 0 from the rows that are not yet filled. The min function picks those zeros, so the totals stay too small. Always check i > 0 and j > 0 before each read, or give the edge cells their own branches as the main program does. The same rule and the same wrap-around are explained in the unique paths lesson.

4. Taking the minimum of the bottom row in the bottom-up method

Students who learn the top-down method sometimes add a scan of the bottom row to the bottom-up method. That is not needed. Bottom-up ends at a single cell, best[0], because every walk passes through the top cell. A scan would return the same value, but it adds work and suggests the method is wrong.

Practice

Exercise 1: A 2 by 2 grid

Find the minimum path sum of this grid:

1 2
1 1

Show the answer

The answer is 3. The route down then right costs 1 + 1 + 1 = 3. The route right then down costs 1 + 2 + 1 = 4, so it is more expensive.

Exercise 2: A small triangle

Find the minimum path sum of this triangle:

1
2 3
4 5 6

Show the answer

The answer is 7. The walk 1, 2, 4 costs 7. The walk 1, 2, 5 costs 8, the walk 1, 3, 5 costs 9, and the walk 1, 3, 6 costs 10.

Exercise 3: The grid with two rows

Find the minimum path sum of the grid below using the one-row version. Write the list after each row.

1 2 3
4 5 6

Show the answer

After the first row, the values are [1, 3, 6]. In the second row, the first cell is 4 + 1 = 5. The second cell is 5 + min(3, 5) = 8. The third cell is 6 + min(6, 8) = 12, so the list is [5, 8, 12]. The answer is 12, from the route right, right, down: 1 + 2 + 3 + 6 = 12.

Exercise 4: Why the bottom-up list has a fixed length

The bottom-up function creates best as a copy of the bottom row, so it has as many entries as the bottom row. After it processes row r, how many of the entries in best does it still need, and why are the others harmless?

Show the answer

After it processes row r, only the first r + 1 entries hold useful values. The next row up has r entries, and its loop reads positions 0 through r, so the entries after that are never read. The unused entries take up a little memory but do not change the answer.

Exercise 5: A five-row triangle

Find the minimum path sum of this triangle:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Show the answer

The answer is 17. The best walk is 7, 3, 1, 4, 2. Working up from the bottom row, row 3 gives [6, 9, 6, 9], row 2 gives [14, 7, 6], row 1 gives [10, 14], and row 0 gives 17.

Summary

• The cheapest grid route is found by filling a table where each cell takes the cheaper of its neighbour above and its neighbour to the left, plus its own cost.
• The top row and left column need their own rules, because they have only one neighbour.
• A grid table can be shrunk to one row because each cell reads only the row above and the cell to its left.
• A triangle is solved bottom-up: each cell adds the smaller of the two cells directly below it.
• Bottom-up ends at a single cell, so no scan of the last row is needed, and one list can hold the current row.
• Walking a row from right to left in the bottom-up method reads values that were already replaced, and it gives a wrong answer without an error.