120. Triangle — DSA Atlas

120

MediumTwo-Dimensional Dynamic Programming2D dynamic programming compressed to one rolling rowBottom-up triangle path DP

Triangle

Given a triangle array where row i has i+1 numbers, return the minimum path sum from the top to the bottom. From index j in a row you may move to index j or index j+1 in the next row (adjacent numbers below).

Open official problem prompt ↗

In plain English

Find the cheapest way to descend from the single top element to the bottom row, stepping only to adjacent elements each level.

Picture it like this

Picture water starting at the peak of a pyramid, at each step trickling to one of the two stones immediately below. You want the route where the summed weights of stones touched is smallest.

Example

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Why: The path 2 -> 3 -> 5 -> 1 sums to 11, the smallest top-to-bottom total.

Constraints

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

Pattern lesson

See the pattern, then code

Bottom-up triangle path DP

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Working from the bottom up, the best total achievable from a cell is its own value plus the smaller of the two reachable cells directly below. Collapsing upward leaves the answer at the apex.

New words, made simpleKnow these before the algorithm

Adjacent move: From position j you may go to j or j+1 in the next row
Bottom-up DP: Solving from the base toward the apex so each cell's successors are already final
Rolling row: A single 1D array reused per level instead of a full 2D table

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Top-down recursion

Recomputes shared sub-triangles exponentially.

From the apex recurse into both children and take the min, summing values.

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

Best choiceBottom-up rolling DP

Linear-space, single pass; each cell solved once from finalized children.

Overwrite a 1D array from the last row upward, each cell adding the smaller child.

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

The rule we keep true

Invariant

After processing row i, dp[j] holds the minimum path sum from cell (i, j) down to the bottom row.

Why this is correct

Reasoning

The minimum descent from a cell must step to one of its two children, so it equals the cell's value plus the smaller child's already-optimal descent. Processing rows bottom-up guarantees both children are finalized before the parent, so induction gives the apex the global minimum.

The algorithm in three movesSay these aloud before coding

1Start dp as a copy of the last row

dp = [4,1,8,3] (bottom row)

2Move upward row by row

row2 -> dp = [7,6,10]

3For each cell add its value to the min of the two dp entries below it

row1 -> dp = [9,10] then apex -> 11

4The apex dp[0] holds the minimum total

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readbottom row [4,1,8,3]

2 · AskWhat is the base of the DP?

3 · Update statedp = [4, 1, 8, 3]

4 · ResultCosts from each bottom cell are themselves

Key takeaway

The triangle flattened row by row; highlighted cells 2,3,5,1 form the optimal descending path.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Seed with the base
dp starts as a copy of the last row, the natural DP base.
2
Lines 4-6Climb upward
For each higher row, replace dp[j] with the cell value plus the smaller of dp[j] and dp[j+1] below.
3
Lines 7Return apex
dp[0] now holds the minimum total from top to bottom.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single-element triangle returns that element
Negative numbers are allowed and must be included in the min correctly
Two-row triangles reduce to top plus the smaller of two

Common beginner mistakes

Going top-down without memoization and timing out
When rolling in place from the top, you would clobber values still needed; going bottom-up avoids this
Off-by-one on the child indices j and j+1

Check your understanding

Why does processing from the bottom row upward let us reuse a single 1D array safely?

Triangle

Triangle

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming