Cheapest Path Down a Triangle

A triangle of numbers is given as a list of rows: the first row holds 1 number, the second 2, the third 3, and so on. You start at the top and move down one row at a time. From position j in a row you may step to position j or position j + 1 in the row below.

Write min_path(triangle) that returns the smallest possible sum of the numbers on a path from the top row to the bottom row.

Examples

min_path([[5], [9, 6], [4, 6, 8], [0, 7, 1, 5]])  # returns 18
min_path([[1], [2, 3], [9, 4, 1], [9, 9, 9, 1]])  # returns 6
min_path([[-3]])                                  # returns -3

In the second example, always stepping to the smaller number below gives 1 + 2 + 4 + 9 = 16, but the path 1 + 3 + 1 + 1 = 6 is cheaper.

Constraints

• The triangle has 1 to 300 rows.
• -10000 <= triangle[i][j] <= 10000