158. Triangle

Medium · Dynamic Programming

You are given a triangle of numbers arranged in rows, where row i contains i+1 numbers. Starting from the top, find the minimum sum path to the bottom, where each step moves to an adjacent number in the row below (you can move to the element directly below or diagonally below-right). Return the minimum possible sum.

Input: An array of rows representing the triangle, where triangle[i] is an array of i+1 numbers.

Output: Return a single integer representing the minimum path sum from top to bottom.

Examples

Example 1
Input: [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: 2 + 3 + 5 + 1 = 11 is the minimum path
Example 2
Input: [[-10]]
Output: -10
Explanation: Single element triangle

Constraints