Triangle

Implement minimumTotal

Given a triangular arrangement of numbers, and starting at the single value on top, find the minimum possible sum of any path down to the bottom row — where each step from a value moves to one of the two values directly below it in the next row (either straight down or one position to the right). This platform's judge accepts the triangle as a square n×n grid: row i's first i+1 entries are the real triangle values, and any remaining entries in that row are unused padding. Every position's cheapest finish depends only on the two positions reachable from it one row down, so working from the bottom row upward — where a value's cheapest finish is just itself — lets each row above be resolved using results the sweep already computed. By the time the sweep reaches the single apex value, it holds the minimum total for the entire triangle.

Example 1:

Input: triangle = [[1,0,0,0],[4,2,0,0],[3,6,5,0],[9,7,8,2]]

Output: 10

Example 2:

Input: triangle = [[5,0],[2,3]]

Output: 7

Example 3:

Input: triangle = [[-7]]

Output: -7

+ 7 hidden test cases run on Submit.

Constraints:

  • 1 ≤ number of rows in the triangle ≤ 20
  • -1000 ≤ each triangle value ≤ 1000
  • The triangle is passed as a square n×n grid: row i holds i+1 real values followed by unused padding (use 0) out to column n-1

triangle =

[[1,0,0,0], [4,2,0,0], [3,6,5,0], [9,7,8,2]]