DSA problem
Triangle
Given a triangle array, return the minimum path sum from top to bottom. At each step you may move to an adjacent number in the row below — that is, from index j in the current row you may go to index j or index j + 1 in the next row.
The triangle has n rows where row i (0-indexed) contains exactly i + 1 numbers. So a path is a sequence of n values, one per row, with each subsequent index increasing by 0 or 1. Equivalently, a path corresponds to a sequence of n - 1 "stay or step right" decisions.
A top-down DP works — dp[i][j] = triangle[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j]) with care at row boundaries — but it inverts the natural flow. The cleaner formulation is bottom-up: let dp[j] be the minimum sum from the bottom row up to cell (i, j). Initialize dp to the last row of the triangle. For each row i from n - 2 down to 0, update dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) for j from 0 to i.
This bottom-up approach has two clean advantages: it removes the row-boundary special cases (the only adjacency at the bottom is "j" and "j + 1", always inside the previous row), and it reuses a single 1-D array of length n rewritten in place. The final answer is dp[0]. Total cost is O(n^2) time and O(n) space.
Examples
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]11triangle = [[-10]]-10triangle = [[1],[2,3]]3Constraints
- 1 <= triangle.length <= 200
- triangle[0].length == 1 and triangle[i].length == triangle[i - 1].length + 1.
- -10^4 <= triangle[i][j] <= 10^4
- At each step you may move to index `j` or `j + 1` in the next row.
- The result must be the sum of one valid top-to-bottom path.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.