Down the Triangle

Difficulty: 1400 2000 ms 128 MB

dp

Starting at the apex of a number triangle, each step moves to one of the two numbers below. Minimize the sum of the visited numbers.

Input: the first line has N; row i (1-based) of the next N lines has i integers.

Output: the minimum path sum from apex to base.

Constraints:

• 1 ≤ N ≤ 500
• |values| ≤ 100

Sample Tests

4
2
3 4
6 5 7
4 1 8 3

11

1
-5

-5

Read the Editorial Statistics