Given a triangle of integers, return the minimum path sum from the top to the bottom, moving only to adjacent numbers on the next row. Pattern focus: Min path sum. The triangular structure is a compact 2D dynamic programming problem.
triangle is a lower-triangular matrix
minimum triangle path sum
Example 1:
Input:
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output:
11
Explanation:
The minimum path sum in the triangle is 11.
Example 2:
Input:
triangle = [[-10]]
Output:
-10
Explanation:
A one-row triangle returns its only value.
Example 3:
Input:
triangle = [[1],[2,3],[3,6,7],[8,9,6,1]]
Output:
12
Explanation:
The optimal route sums to 12.