120. Triangle - LeetCode Solution

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:

        dp = []

        for i in range(len(triangle) + 1):
            k = []
            for j in range(len(triangle) + 1):
                k.append(-1)
            dp.append(k)


        def trav(i, j):
            if i >= len(triangle):
                return 0

            if j >= len(triangle[i]):
                return 0

            if dp[i][j] != -1:
                return dp[i][j]

            dp[i][j] = min(trav(i + 1, j) + triangle[i][j], trav(i + 1, j + 1) + triangle[i][j])
            return dp[i][j]


        return trav(0, 0)