1 minute read

120. Triangle

Difficulty: Easy

Related Topics: Array, Dynamic Programming

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]] Output: -10

Code:

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

Feedbacks:

First, I worked on the basecases. If triangle has more than 3 rows, I create a duplicate list of triangle list. Then as I traverse through the list, I compare the lowest value from the higher row and add it to value. Then I can get the minimum path sum at the last row of the triangle list.*

You may also enjoy