Accepted solution in Python


  • 0
    L

    The code is based on dynamic programming. Let me know if you have any comments on improving it.

    class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        mintmp=[0]*len(triangle)
        mintmp[0]=triangle[0][0] # initialized for the first layer
        for i in range (1,len(triangle)):
            mintmp[i]=mintmp[i-1]+triangle[i][i] # update the largest note
            for j in range(i-1,0,-1): # reversely update all the notes
                mintmp[j]=min(mintmp[j-1],mintmp[j])+triangle[i][j]
            mintmp[0]=mintmp[0]+triangle[i][0] # update the lowest one
        return min(mintmp)

  • 2
    R

    DP in place solution, bottom up direction, updates nodes by adding minimum of two underlying nodes

    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        def minimumTotal(self, triangle):
            for level in range(1, len(triangle))[::-1]:
                for i in range(0, len(triangle[level]) - 1):
                    triangle[level-1][i] += min(triangle[level][i], triangle[level][i+1])
            
            return triangle[0][0]
    

    DP with O(n) extra space, if no changes in original triangle allowed, the same idea, using temporary array to store calculated minimal sums

    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        def minimumTotal(self, triangle):
            tmp = triangle[len(triangle) - 1]
            for level in range(1, len(triangle))[::-1]:
                for i in range(0, len(triangle[level]) - 1):
                    tmp [i] = triangle[level-1][i] + min(tmp[i], tmp[i+1])
    
            return tmp[0]
    

  • 0
    L

    Thanks radovan! Your solution that use triangle itself to store the intermediate minimum sum is great! Also bottom up is a super awesome idea! No boundary problem and the need to calculate the minimum value. Thanks for sharing!

    IMHO, if later the path need to be determined, I am afraid, the code need to have additional space and calculate from top to bottom.


Log in to reply
 

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