Triangle

main.md

Question

Approach

I solve it with dynamic programming from the bottom up. I keep a 1D array dp representing the minimum path sums from the current row down to the bottom; I initialize dp to the last row of the triangle. Then I iterate upward row by row: for each element triangle[i][j] I update dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). After processing the top row, dp[0] holds the answer.

Implementation

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

        dp = triangle[-1][:]

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

        return dp[0]

Complexities

• Time: O(N)
• Space: O(m)