Triangle

The key idea

The best total to reach the bottom from cell (i, j) is its own value plus the smaller of the two best totals below it: triangle[i][j] + min(below[j], below[j+1]). Solve from the bottom row up so each cell already knows the best of its two children.

Problem

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Constraints

1 <= triangle.length <= 200
triangle[i].length == i + 1
-10^4 <= triangle[i][j] <= 10^4

Examples

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11

Input: triangle = [[-10]] Output: -10

Complexity

Time: O(n^2) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →