Beat 100% Python submission solution (O(n) space also)!


  • 0
    Z
    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
            
            if not triangle:
                return 0
            
            n = len(triangle)
            
            if n == 1:
                return triangle[0][0]
            
            prev = triangle[0]
            
            for i in xrange(1, n):
                current = [0]*(i+1)
                for j in xrange(i+1):
                    if j == 0: current[0] = triangle[i][0] + prev[0]
                    elif j == i: current[i] = triangle[i][i] + prev[-1]
                    else:
                        current[j] = min(triangle[i][j] + prev[j-1], triangle[i][j] + prev[j])
                prev = current
            
            return min(current)

Log in to reply
 

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