[LeetCode] 120. Triangle

Problem : https://leetcode.com/problems/triangle/

Memorization Solution:

Time Complexity = O ( N ** 2 - 1)   N = Len(triangle)

Space Complexity = O ( N ** 2 - 1)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        level = len(triangle)
        
        @lru_cache(maxsize = None)
        def path(y, x):
            if y == level - 1:
                return triangle[y][x]
            
            return triangle[y][x] + min(path(y+1,x), path(y+1, x+1))
        
        return path(0,0)

Bottom-to-Top Solution:

Time Complexity = O ( N ** 2 - 1)   N = Len(triangle)

Space Complexity = O ( N )

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