Triangle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n_row = len(triangle)
        dp = [[] for _ in range(n_row)]
        dp[0].append(triangle[0][0])

        for i in range(1, n_row):
            for j in range(i+1):
                top_left = dp[i-1][j-1] if j-1>=0 else float("inf")
                top_right = dp[i-1][j] if j < len(triangle[i-1]) else float("inf")
                minimal = min(top_left, top_right) + triangle[i][j]
                dp[i].append(minimal)
        return min(dp[-1])