You are given triangle array.
Write a script to find the minimum path sum from top to bottom.
When you are on index `i` on the current row then you may move to either index `i` or index `i + 1` on the next row.
Examples
Example 1
Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
Output: 8
Explanation: The given triangle
1
2 4
6 4 9
5 1 7 2
The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
[1]
[2] 4
6 [4] 9
5 [1] 7 2
Example 2
Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
Output: 7
Explanation: The given triangle
3
3 1
5 2 3
4 3 1 3
The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
[3]
3 [1]
5 [2] 3
4 3 [1] 3
Overview
We will read in the data, and put it in a (2-dimensional) array. We will then work from bottom to top, calculating for each point, the minimum path length to the bottom. We can do this by adding the minimum of the two elements "below" the current element to it.
For instance, assume the input is:
3
3 1
5 2 3
4 3 1 3
we can calculate the minimum path length to the bottom for the penultimate row by, for each element in that row, adding to it the minimum of the two elements below. This results in:
3
3 1
8 3 4
4 3 1 3
In the same way, we can calculate the minimum path length for each element in the second row:
3
6 4
8 3 4
4 3 1 3
One more step, and we get the wanted result in the top of the triangle:
7
6 4
8 3 4
4 3 1 3
This clearly is a linear time algorithm.
Solutions
Each of the solutions assumes a single triangle on standard input, one row per line, numbers separated by white space. We’re assuming the numbers are integers. The result, as single number, will be written on standard output.
Perl
We start with reading in the data, which can be done in a single statement:
my @nums = map {[/-?[0-9]+/g]} <>;
For each line of input, we’re extracting the numbers using a simple regular expression. This stores the triangle of numbers in the array @nums; each element of @nums is an array with numbers (a row in the triangle).
We can now calculate the lengths using a nested loop; the other loop loops over the rows (bottom to top, starting with the penultimate row), the inner loop loops over the elements of a row.
for (my $x = @nums - 2; $x >= 0; $x --) {
foreach my $y (keys @{$nums [$x]}) {
$nums [$x] [$y] +=
$nums [$x + 1] [$y] < $nums [$x + 1] [$y + 1]
? $nums [$x + 1] [$y] : $nums [$x + 1] [$y + 1]
}
}
For each element, we adding the minimum of the two elements below it.
All what needs to be done is to print the result:
say $nums [0] [0];
Find the complete program on GitHub.
