120. Triangle

Problem¶

Given a numeric triangle, find the minimum sum of a path from its top to bottom. From position (r, c), the next position must be (r + 1, c) or (r + 1, c + 1).

triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
path     = 2 -> 3 -> 5 -> 1
output   = 11

Key trick¶

Work bottom-up: the minimum cost from each cell is its value plus the smaller minimum cost of its two children. One row of DP is sufficient.

Trap¶

• A greedy choice of the smaller immediate child may miss the globally optimal path.
• Top-down in-place DP can overwrite values still needed unless updated right-to-left or carefully preserved.
• Negative values invalidate assumptions that extending a path always increases its sum.

Why is it interesting?¶

It compresses a natural two-dimensional recurrence into \(O(n)\) extra space by observing that each row depends only on the adjacent row.

Python solution¶

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        # dp[c] is the minimum path sum from the current cell to the bottom.
        dp = triangle[-1][:]

        for r in range(n - 2, -1, -1):
            for c in range(r + 1):
                dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])

        return dp[0]

Time complexity: \(O(n^2)\) for \(n\) rows.

Space complexity: \(O(n)\).

Comment on my solution¶

Your solution is correct and meets the \(O(n)\) space requirement. Saving dp[c] in cur and the previous old value in prev prevents left-to-right updates from destroying required state.

The main drawback is that prev is established implicitly during the first column of every row, making the invariant less obvious and easier to break during modification. The bottom-up formulation avoids boundary cases and removes the final min(dp), so it is generally easier to explain in an interview.

# ideas
# - turn a 2D rec formula into one-dimensional DP
#   - (r > 0, c > 0) dp[r][c] = min(dp[r-1][c-1], dp[r-1][c]) + triangle[r][c]
#
# 2
# 3 4
# 6 5 7
# 4 1 8 3

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        dp = [0] * n
        dp[0] = triangle[0][0]

        for r in range(1, n):
            for c in range(r + 1):
                cur = dp[c]
                if c == 0:
                    dp[c] += triangle[r][0]
                elif c == r:
                    dp[c] = prev + triangle[r][c]
                else:
                    dp[c] = min(prev, cur) + triangle[r][c]
                prev = cur
        return min(dp)