Triangle Minimum Path Sum
Find the cheapest way down a triangle of numbers, one step to the row below at a time.
Given a triangle
Example 1
Output: 11
Explanation: the path 2, 3, 5, 1 adds up to 11.
Example 2
Output: -10
The Idea
Picture a pyramid of numbered blocks. You start on the block at the top and climb down one row at a time, and from each block you may step onto one of the two blocks right under it. Every block you stand on adds its number to your total, and you want the smallest total at the bottom.
Write Example 1 as a pyramid. The top block is 2, and under it sit 3 and 4. Under 3 sit 6 and 5, and under 5 sit 1 and 8. The walk 2, 3, 5, 1 adds up to 11, and no other walk down does better. With four rows there are eight walks in all, because each of the three steps has two choices.
Why not just step onto the smaller block each time? In Example 1 that happens to give 2, 3, 5, 1. But take the pyramid [[1], [2, 3], [9, 9, 1]]
So the choice at a block depends on what lies below it. That suggests starting at the bottom. For a block in the bottom row, the cheapest way down is just its own number. For a block one row higher, it is its own number plus the cheaper of the two blocks under it.
Look at the picture above. On the left is the triangle from Example 1, with the cheapest path 2 + 3 + 5 + 1 in orange. On the right, headed “cheapest sum from this cell down”, each block holds the best total from that block to the bottom. Row 3, the bottom row, keeps its own numbers. In row 2, the block 5 becomes 5 + min(1, 8) = 6, as the first teal line under the picture shows.
Row 1 works the same way: 3 + min(7, 6) = 9 and 4 + min(6, 10) = 10. At the top, 2 + min(9, 10) = 11, which is the answer. Each block was worked out once, and the row above simply read the two numbers under it.
Working out the best total for each block once, and letting the blocks above build on those totals instead of walking every path again, is called dynamic programming.
Solution Approach
Turning that idea into code means looking at why trying every path is slow, then settling two things: which direction to fill the rows, and where to keep the totals.
Trying every path
How many paths are there? Each step down offers two choices, so a triangle with n rows has 2n-1 paths: 8 for Example 1, but more than 500,000 for 20 rows. A search that walks each one adds up the same lower parts again and again, since many paths pass through the same block.
Filling the rows from the bottom up
Which row should come first? The best total for a block needs the two totals under it, so the bottom row comes first and the top row last. A block at row r, index i, gets its own number plus the smaller of the totals at index i and index i + 1 in row r + 1.
Going upward also ends neatly. The top row has a single block, so its total is the answer, and there is no need to compare several end points at the bottom.
Working from the top down is possible too, with a method that calls itself for the two blocks below and remembers each result. It finds the same totals, but needs a table for the stored results and a call for each block.
One array for the totals
Do we need a whole triangle of totals? Each row only reads the row right under it, so a single array, named below
Each row writes its totals over the old ones, from left to right. Writing below[i]
The extra slot lets the bottom row's last block read below[i + 1]below
Java Solution
The method minimumTotal
- First, create the array
withbelow zeros, wheren + 1 is the number of rows.n - Go over the rows from the bottom up with a loop over
, fromr down to 0, and take that row asn - 1 .row - Inside, a second loop moves
over the blocks ofi from left to right. It setsrow to the block's number plus the smaller ofbelow[i] andbelow[i] , the two totals under it.below[i + 1] - When the top row is done,
holds the cheapest total from the top block down, and the method returns it.below[0]
The main[[1], [2, 3], [9, 9, 1]]
import java.util.List;
public class TriangleMinPathSum {
public static int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] below = new int[n + 1]; // cheapest sums from the row below; zeros at first
for (int r = n - 1; r >= 0; r--) {
List<Integer> row = triangle.get(r);
for (int i = 0; i < row.size(); i++) {
// this cell plus the cheaper of the two cells under it
below[i] = row.get(i) + Math.min(below[i], below[i + 1]);
}
}
return below[0];
}
public static void main(String[] args) {
System.out.println(minimumTotal(List.of(
List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3))));
System.out.println(minimumTotal(List.of(List.of(-10))));
System.out.println(minimumTotal(List.of(
List.of(1), List.of(2, 3), List.of(9, 9, 1))));
System.out.println(minimumTotal(List.of(
List.of(-1), List.of(2, 3), List.of(1, -1, -3))));
}
}
Running it prints:
11
-10
5
-1
The 11 and the -10 match Examples 1 and 2. For a triangle with a single row, the outer loop runs once and below[0]
The third line, 5, is the walk 1, 3, 1 through [[1], [2, 3], [9, 9, 1]][[-1], [2, 3], [1, -1, -3]]below
The original implementation,
Complexity
The work is one update of below
- Time: O(n²), because a triangle of n rows has 1 + 2 + ... + n, about n²/2 blocks, and each block costs one addition and one
.Math.min - Space: O(n), because
holds n + 1 totals, one row's worth, while the triangle itself is only read and never copied.below
A square version, where each step down has three choices, is