Triangle
Given a triangle array, return the minimum path sum from top to bottom.
Row 0 holds one number, row 1 holds two, and each row after that holds one more than the row above it. A path starts at the single number in row 0 and takes one number from every row. From row r column c you may move to row r + 1 column c or column c + 1, so each step lands on one of the two numbers directly below.
Input & Output
Input
triangle — the rows of the triangle, top row first, where row r holds r + 1 numbers
Output
the minimum sum of a path from the top row to the bottom row
Example
Input
triangle = [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]Output
11
Explanation
The path 2 → 3 → 5 → 1 sums to 11. Every other top-to-bottom path sums to more.
Example
Input
triangle = [
[-1],
[2,3],
[1,-1,-3],
[5,2,4,1]
]Output
0
Explanation
The best path is -1 → 3 → -3 → 1, which sums to 0. Taking the smaller number at each step instead gives -1 → 2 → -1 → 2, which sums to 2, so a step-by-step greedy choice is not enough.
Constraints
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-10^4 <= triangle[i][j] <= 10^4