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.
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
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.