120. Triangle

Python

Top-Down DP

from functools import cache


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        @cache
        def dp(level, col):
            total = triangle[level][col]
            if level == len(triangle)-1:
                return total

            return total + min(dp(level+1, col), dp(level+1, col+1))

        return dp(0, 0)