Triangle
Medium · 2-D Dynamic Programming · Array · Dynamic Programming
Problem
You are given triangle, a list of rows where row i holds i + 1 integers. Start at the single number on top and move down one row at a time.
From index i in one row you may step to index i or index i + 1 of the next row. Return the smallest possible sum of the numbers on a path from the top row to the bottom row.
Can you do it with only O(n) extra space, where n is the number of rows?
Examples
Input: triangle = [[3],[6,4],[5,1,8],[4,9,2,7]] Output: 10
The path 3 → 4 → 1 → 2 sums to 10, the cheapest route.
Input: triangle = [[-5]] Output: -5
The only path is the top value.
Input: triangle = [[1],[2,3],[9,9,0]] Output: 4
1 → 3 → 0 beats taking the smaller 2 on the second row, which leads only to 9s.
Constraints
- 1 <= len(triangle) <= 200
- len(triangle[0]) == 1
- len(triangle[i]) == len(triangle[i - 1]) + 1
- -10^4 <= triangle[i][j] <= 10^4
Approaches
- Try every path — time O(2^n), space O(n) for the recursion
Follow-up
Can you also return the path itself, not just its sum? Keep the full table (O(n²) space), or store at each cell which child was cheaper; then walk down from the top following those choices.
Related problems
Start free on Cariara · Coding problems · System design studio
