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.

Why this is worth learning

Choose a state with the direction of dependency made explicit: the minimum cost from a position down to the bottom. Then the already-computed row below summarizes every possible suffix.

Before coding: one-minute experiment

If the lower-row costs are [6,5,7] and the current row is [3,4], what are the two new costs? Why is right-to-left overwriting unsafe?

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
• Row r has r+1 values; negative values are allowed.
• For every position, the minimum path sum from that position to the bottom is guaranteed to fit the target Go int.

Core idea (near-solution)

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

Invariant: before updating column c of row r, dp[c] and dp[c+1] are still the two minimum suffix costs in row r+1. Columns before c already hold answers for row r; scan left to right to preserve the old right child.

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

At the bottom, the minimum remaining cost at each position is its own value. For a position (r,c) above it, every valid next move goes to (r+1,c) or (r+1,c+1); choosing the cheaper optimal suffix and adding the current value is both feasible and no worse than any full path. This proves the recurrence by induction upward. Copying the last row keeps the input unchanged. Within a row, update left to right so dp[c] and dp[c+1] are still the two old lower-row values when used. Finally dp[0] summarizes every top-to-bottom path.

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).

Debugging lens

Test negative values and a single-row triangle. Each row must have one more element than the previous. Do not alias the last row as workspace when preserving the input is part of the reference behavior.

Complexity

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

Implementation notes (Go)

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

Contract precision

The input is not modified. The representability guarantee covers each suffix minimum computed bottom-up. Checking only the final answer would be insufficient: later addition of a negative ancestor can hide an earlier oversized suffix. The function has no checked-overflow result.

Reconstruction checkpoint

If the lower-row costs are [6,5,7] and the current row is [3,4], what are the two new costs? Why is right-to-left overwriting unsafe?

Return to 2D DP · Module quiz