120. Triangle

Bottom-up DP collapses to a 1D rolling array. Define the subproblem dp[j] at row i = the minimum path sum from cell (i, j) down to the last row. The recurrence relation is dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) when scanning rows from bottom to top — from cell (i, j) you can step into (i+1, j) or (i+1, j+1). Base case: initialize dp as a copy of the last row. Iterate i from n-2 down to 0, updating dp[j] for j in 0..i (in place is safe because each dp[j] reads the row-below dp[j] and dp[j+1]). Return dp[0]. Time O(n^2) where n is the number of rows; extra space O(n). Top-down is symmetric but requires boundary handling on the diagonal edges.