Problem of The Day: Triangle

Problem Statement

leetcode problem link

Brute Force [Accepted]

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

Editorial

Approach 1: Dynamic Programming (Bottom-up: In-place)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in range(1, len(triangle)):
            for col in range(row + 1):
                smallest_above = math.inf
                if col > 0:
                    smallest_above = triangle[row - 1][col - 1]
                if col < row:
                    smallest_above = min(smallest_above, triangle[row - 1][col])
                triangle[row][col] += smallest_above
        return min(triangle[-1])

Approach 2: Dynamic Programming (Bottom-up: Auxiliary Space)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        prev_row = triangle[0]
        for row in range(1, len(triangle)):
            curr_row = []
            for col in range(row + 1):
                smallest_above = math.inf
                if col > 0:
                    smallest_above = prev_row[col - 1]
                if col < row:
                    smallest_above = min(smallest_above, prev_row[col])
                curr_row.append(triangle[row][col] + smallest_above)
            prev_row = curr_row
        return min(prev_row)