Triangle
Find the minimum path sum from the top of a triangle to the bottom, moving to adjacent numbers on the row below.
Open on LeetCode ↗Intuition
Working top-down feels natural since that is how you read the triangle, but it forces you to track which one or two parents in the row above can reach each cell, plus handling the ragged left and right edges where only one parent exists. Flip the direction: work bottom-up instead. From the second-to-last row upward, every single cell has exactly two children directly below it, no exceptions and no edges to special-case, so dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]) always applies cleanly. The invariant: dp[i][j] is the minimum path sum from cell (i,j) down to the bottom, and by the time you reach row i the row below it is already fully solved. The answer lands in dp[0][0], no post-processing scan required.
Work bottom-up and the branching disappears. From the last row upward, each cell's best total is its own value plus the cheaper of the two cells below — and because the rows shrink, a single array reused in place holds the entire frontier.
Approach
Seed with the bottom row
dp starts as a copy of the triangle's last row -- the minimum path sum from any bottom cell to the bottom is just that cell's own value.
Fill upward
For each row i from the second-to-last up to 0, and each valid column j in that row, set dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) using the dp row just computed for i+1. Every cell has exactly two children, so there are no ragged-edge special cases.
Read the top
After processing row 0, dp[0] is the minimum path sum for the whole triangle -- no scanning or additional comparison needed.
Solution & live demo
Common pitfalls
Going top-down and tracking two adjacency rules
dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
Top-down needs special handling at both ends of each row, where only one parent exists. Bottom-up always has exactly two children in range, so no boundary cases arise at all.
Iterating j upward while overwriting in place
# with a top-down formulation reusing one array
for j in range(i + 1):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])Bottom-up reads dp[j] and dp[j+1] — both still holding the lower row when j ascends, since only indices below j have been rewritten. The direction is safe here precisely because the reads look forward.
Copying the last row by reference
dp = triangle[-1]
dp = triangle[-1][:]
Without the slice, dp aliases the input's last row and the algorithm mutates the caller's data. It still returns the right answer, but the triangle is destroyed — a real bug if the input is reused.
Edge cases
The loop never runs; the answer is simply that one value.
min() still correctly favors the least (most negative) sum since no sign assumption is baked into the recurrence.
One iteration of the upward fill directly produces dp[0] = triangle[0][0] + min of the two bottom values.
min() picks either equally-valid path; the resulting sum is identical either way.