Triangle Minimum Path Sum

Triangle Minimum Path Sum is a classic dynamic programming problem, often appearing in Oracle interviews with tags Array and Dynamic Programming.[1][7]

Problem Statement

Given a triangle array, return the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below, meaning from position (row, j) you can go to (row+1, j) or (row+1, j+1).[7][1]

Input/Output Examples

Example 1:
Input: triangle = [,,,][2][3][4][5][6][8][1][7] Output: 11
Explanation: The minimum path is 2 → 3 → 5 → 1 (sum = 11).[5][1]

Example 2:
Input: triangle = [,,][3][6][9][1][2][7] Output: 11
Explanation: The minimum path is 2 → 3 → 6 (sum = 11), or other paths like 2 → 3 → 1 also sum to 11.[1]

Constraints

• 1 ≤ triangle.length ≤ 200
• triangle[i].length = i + 1
• -10^4 ≤ triangle[i][j] ≤ 10^4[7]