Python solution with detailed explanation

  • 0




    • 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.