Down the Triangle
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
Input 1
4 2 3 4 6 5 7 4 1 8 3
Output 1
11
Input 2
1 -5
Output 2
-5
Discussion (opens after you solve — no spoilers before)
No comments yet.