1138. Triangle — Minimum Path Sum Top to Bottom

Given a triangle as a list of rows (row i has i+1 numbers), find the minimum path sum from top to bottom, where from index j in a row you may move to index j or j+1 in the next row. Return that minimum sum. The input is JSON {triangle}.

Input: JSON {triangle}.

Output: Integer — the minimum top-to-bottom path sum.

Examples

Input: {"triangle":[[2],[3,4],[6,5,7],[4,1,8,3]]}
Output: 11
Explanation: 2+3+5+1 = 11.

Input: {"triangle":[[-10]]}
Output: -10
Explanation: Single element.

Input: {"triangle":[[1],[2,3]]}
Output: 3
Explanation: 1+2 = 3.

Constraints

• 1<=rows<=200

Asked by