Minimum sum path in a triangle

Problem Given a triangle (row i has i+1 numbers), find the minimum top-to-bottom path sum; from (i, j) you may step to (i+1, j) or (i+1, j+1).

Input / Output

• Input: List<List<Integer>> triangle. Output: min path sum.

Constraints

• Up to 200 rows; O(n^2) time; the follow-up asks for O(n) extra space.

Example

• [[2],[3,4],[6,5,7],[4,1,8,3]] → 11 (2+3+5+1).

Expected approach

• Bottom-up DP is the clean answer: start from the last row, dp[j] = tri[i][j] + min(dp[j], dp[j+1]) sweeping rows upward; dp[0] is the answer — naturally O(n) space, no boundary special-casing (top-down needs edge handling at j=0 and j=i). O(n^2) time. Greedy fails (local min steps miss the global path) — standard probe. In-place on the triangle if mutation is allowed.