Show problems as
Classic problem #120MediumArrayDynamic Programming

Triangle

Real-world version: Sensor Cascade Minimum
Tracked in this browser only
Read Triangle on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A drift monitor prints its readings as a growing stack of rows. Row 0 holds one reading, and every later row holds exactly one more reading than the row above it, so row i holds i + 1 readings. Each reading is a signed drift in millidegrees and may be negative.

A trace begins on the single reading in row 0 and ends on some reading in the last row. From reading j of row i, a trace may continue to reading j or to reading j + 1 of row i + 1. The weight of a trace is the sum of every reading it lands on, including the first and the last.

Given rows, return the smallest weight any trace can have.

Examples

Example 1

Input
rows = [[3],[1,7],[10,10,0]]
Output
10

The trace 3 -> 7 -> 0 starts on the only reading of row 0, moves to reading 1 of row 1 and then to reading 2 of row 2, so every hop is allowed. Its readings add to 10.

Example 2

Input
rows = [[2],[5,-3],[1,-1,4],[0,2,-6,3]]
Output
-8

The trace 2 -> -3 -> -1 -> -6 keeps to indices 0, 1, 1, 2, and each hop either holds the index or raises it by one. The four readings add to -8.

Constraints

  • 1 <= rows.length <= 200
  • rows[0].length == 1
  • rows[i].length == rows[i - 1].length + 1
  • -10^4 <= rows[i][j] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def cheapest_cascade(rows: list[list[int]]) -> int:
Java
public int cheapestCascade(List<List<Integer>> rows)

More on the same topics