Problem Id: 120 Difficulty: Medium Tag: Array Tag: Dynamic Programming


We could update the triangle in down-top order. For each number, we would update it to the minimum path sum from it to bottom.

By modifying it in place, this could be solved with O(1) extra space.


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if not triangle:
            return 0

        for row in range(len(triangle) - 2, -1, -1):
            for i in range(row + 1):
                triangle[row][i] += min(triangle[row + 1][i], triangle[row + 1][i + 1])
        return triangle[0][0]