Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every path reaching a cell must come from one of the two adjacent cells above it. If we already know the cheapest path to each possible parent, the cheapest path to the current cell is its value plus the smaller parent cost. Negative values do not change this recurrence because paths always move down to a new row.

Approach

Leave the top entry unchanged: it is the only path to the first row.
Process later rows from top to bottom, replacing each value with the minimum path sum ending there.
The left boundary has only the parent directly above, and the right boundary has only the upper-left parent. For an interior entry, add the smaller of those two parent sums.
Return the minimum value in the last row, since a valid path may end anywhere along the bottom. The input triangle itself stores the dynamic-programming states.

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                if j == 0:
                    triangle[i][j] += triangle[i - 1][j]
                elif j == len(triangle[i]) - 1:
                    triangle[i][j] += triangle[i - 1][j - 1]
                else:
                    triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1])

        return min(triangle[-1])

Complexity analysis

Let N be the total number of triangle entries. Both displayed implementations use in-place row-by-row dynamic programming, taking O(N) time and O(1) auxiliary space beyond the mutated triangle.