[Leetcode][python] 120: triangle - DP

• Leetcode 120: Triangle
• Level: Medium
• Link

Triangle - LeetCode

My Approach

1. Sum up the previous lists values to the current list
2. For the first element and the last element, add up the first element of the last element of the list before.
3. Continue until the last list
4. Return the minimum value of the last list

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