mediumDynamic Programming 2DPure DSA~20 min
Minimum Path Sum Down a Triangle
A triangular schedule of stage costs grows by one cell per row. Starting at the apex you descend to an adjacent cell each step. Find the minimum total cost to reach the bottom.
Problem
Given a triangle as a list of rows where row r has r+1 elements, return the minimum path sum from top to bottom. From index i in a row you may move to index i or i+1 in the next row.
Input
A list triangle of integer rows of increasing length.
Output
An integer: the minimum top-to-bottom path sum.
Constraints
- 1 <= triangle.length <= 200
- -10^4 <= triangle[r][c] <= 10^4
Examples
Example 1
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
2 -> 3 -> 5 -> 1 sums to 11.
Example 2
Input
triangle = [[-10]]
Output
-10
A single-cell triangle.