Minimum sum path in a triangle

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

Input / Output

• Input: List<List<Integer>> triangle.
• Output: the minimum path sum from the apex to the bottom row.

Constraints

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

Example

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