Triangle

Given a triangle array, return the minimum path sum from top to bottom. At each step you may move to adjacent numbers on the row below.

Function signature

func MinimumTotal(triangle [][]int) int

Inputs / outputs

• triangle: list of rows, row i has i+1 elements.
• Return: minimum path sum.

Example

[2]
[3,4]
[6,5,7]
[4,1,8,3]
Minimum path: 2 + 3 + 5 + 1 = 11

Constraints

• 1 <= number of rows <= 200

Core idea (near-solution)

Bottom-up DP: start from the last row and collapse upward using min of adjacent children.

Invariant: dp[c] is the minimum total from row r+1 at position c.

Algorithm (step-by-step)

1. Copy the last row into dp.
2. For r from n-2 down to 0:
   • For c in 0..r: dp[c] = min(dp[c], dp[c+1]) + triangle[r][c].
3. Return dp[0].

Correctness sketch

• Invariant: dp[c] is the minimum total from row r+1 at position c.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
[2]
[3,4]
[6,5,7]
[4,1,8,3]
Minimum path: 2 + 3 + 5 + 1 = 11

Walk:
- bottom row: [4,1,8,3]
- row2: [6,5,7] -> [7,6,10]
- row1: [3,4] -> [9,10]; row0: [2] -> [11]

Pitfalls to avoid

• Mutating the original triangle if not allowed.
• Using top-down without memoization (exponential).

Complexity

• Time: O(n^2).
• Extra space: O(n).

Implementation notes (Go)

• Use a 1D slice for dp to keep memory small.