120. Triangle
You are given a triangle of integers: a list of rows where row i holds exactly i + 1 values. Starting from the single number at the top, you descend one row at a time. From position j in a row you may step only to position j or position j + 1 in the row below — straight down, or down-and-right.
Your function receives the triangle and returns the smallest possible sum of the values collected along a full top-to-bottom path.
Values can be negative, so a path that looks expensive early may still win. Greedy 'take the smaller child' fails; think about what the best answer from each cell downward looks like. Bonus goal: solve it with only O(n) extra space, where n is the number of rows.
Example 1:
Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Output: 11
Explanation: The cheapest descent is 2 → 3 → 5 → 1, which costs 11. Every step moves to the same index or one index to the right.
Example 2:
Input: triangle = [[-10]]
Output: -10
Explanation: With one row there is nothing to choose — the answer is the lone value.
Constraints:
- 1 ≤ n (number of rows) ≤ 200
- Row i contains exactly i + 1 values (0-indexed).
- -10⁴ ≤ each value ≤ 10⁴
Hints:
Greedy fails: the smaller of the two children may lead into an expensive region. You need the best full continuation, not the best next step.
Define best(r, c) = the cheapest sum from cell (r, c) to the bottom. Then best(r, c) = triangle[r][c] + min(best(r+1, c), best(r+1, c+1)), and the bottom row is its own answer. Memoize and the exponential tree of paths collapses to one evaluation per cell.
Run it bottom-up instead: start with a copy of the last row and fold upward. One array of size n suffices because row r only ever reads slots c and c + 1 — the answer ends up in slot 0.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Expected output: 11