Python solution with detailed explanation


  • 0
    G

    Solution

    Triangle https://leetcode.com/problems/triangle/?tab=Description

    Memoization

    • f[n,i] = min(f[n+1,i], f[n+1,i+1]) + mat[n,i] for n <= N-1
    • return 0 for n=N
    • For space of order N, we can use a DP solution where we store the minimum sum for every index. We do not require information of previous rows.
    from collections import defaultdict
    class Solution(object):
        def helper(self, triangle, row, col, cache):
            N = len(triangle)
            if row == N:
                return 0
            if row in cache and col in cache[row]:
                return cache[row][col]
            cache[row][col] = min(self.helper(triangle, row+1, col, cache), self.helper(triangle, row+1, col+1, cache)) + triangle[row][col]
            return cache[row][col]
        
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
            return self.helper(triangle, 0, 0, defaultdict(dict))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.