Leetcode 120. Triangle

minimum_output_triangle.py

# top-down: Larger Number TLE
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 1:
            return triangle[0][0]
        res = tuple()
        level = 0
        curr_list = triangle[level]
        next_level = level + 1
        next_list = triangle[next_level]
        for idx in range(next_level):
            for offset, each_num in enumerate(next_list[idx:idx+2]):
                res += (self.doMinTotal(each_num + curr_list[idx], offset+idx, next_level, triangle),)
        return min(res)
    
    def doMinTotal(self, ans: int, start_idx: int, level: int, triangle: List[List[int]]) -> int:
        next_level = level + 1
        if next_level == len(triangle):
            return ans
        res = tuple()
        next_list = triangle[next_level]
        for offset, each_num in enumerate(next_list[start_idx:start_idx+2]):
            res += (self.doMinTotal(ans + each_num, start_idx + offset, next_level, triangle),)
        return min(res)


# Bottom-up, Efficient
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 1:
            return triangle[0][0]
        for level in range(len(triangle) - 1, 0, -1):
            curr_list = triangle[level]
            prev_list: List[int] = triangle[level-1]
            for idx in range(level):
                triangle[level-1][idx] += min(curr_list[idx: idx+2])
        return triangle[0][0]