All problems

Triangle

Medium · dynamic programming

A pyramid is built from stepping stones. The top row has 1 stone, the next row has 2, and so on, so row i (counting from 0) has i + 1 stones. Each stone has a number written on it.

A climber starts on the single stone at the top and walks down to the bottom row. From the stone at position j in one row, the climber may step to the stone at position j or position j + 1 in the row directly below.

Add up the numbers on every stone the climber stands on, including the first and the last. Return the smallest total of any walk from the top stone to any stone in the bottom row.

Examples

Example 1

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

Output: 11

The walk 2, 3, 5, 1 adds up to 11. No other walk is smaller.

Example 2

Input: triangle = [[-5]]

Output: -5

A pyramid with one stone has one walk.

Example 3

Input: triangle = [[1], [-2, -3]]

Output: -2

Stepping down to the stone with -3 gives 1 + -3 = -2, which beats 1 + -2 = -1.

Constraints