Description
Given a triangle array, return the minimum path sum from top to bottom. At each step, you may move to adjacent numbers on row below.
Examples
Input:
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]Output:
11Explanation:
2+3+5+1=11.
Input:
triangle = [[-10]]Output:
-10Explanation:
Works with negative numbers.
Input:
triangle = [[1],[2,3],[4,5,6],[7,8,9,10]]Output:
14Explanation:
The minimum path is 1→2→4→7=14. At each level, choosing the adjacent element that leads to the smaller sum: from 1 it is possible to go to 2 or 3 (choose 2), from 2 it is possible to go to 4 or 5 (choose 4), from 4 it is possible to go to 7 or 8 (choose 7).
Constraints
- •
1 ≤ triangle.length ≤ 200