Minimum Path Sum in a Triangle

Given a triangle of numbers, find the minimum path sum from the top to the bottom. At each step, you are allowed to move to one of the two adjacent numbers in the row immediately below.

The triangle is provided as a flattened list with the number of rows given first. For a triangle with n rows, the total number of entries in the list is \(\frac{n(n+1)}{2}\).

If we denote the value at row \(i\) and column \(j\) as \(a_{i,j}\), then the minimum path sum from the top element \(a_{1,1}\) is computed using the recurrence:

$$f(i, j) = a_{i,j} + \min\{f(i+1,j),\; f(i+1,j+1)\},$$

with the base condition being the elements in the last row.

inputFormat

The input is read from stdin and consists of two parts:

• The first line contains an integer n, representing the number of rows in the triangle.
• The second line contains \(\frac{n(n+1)}{2}\) space-separated integers that represent the flattened triangle.

outputFormat

Output to stdout a single integer, which is the minimum path sum from the top to the bottom of the triangle.

4
2 3 4 6 5 7 4 1 8 3

11