Python easy to understand solutions (top-down, bottom-up).


  • 26
    C
    # O(n*n/2) space, top-down 
    def minimumTotal1(self, triangle):
        if not triangle:
            return 
        res = [[0 for i in xrange(len(row))] for row in triangle]
        res[0][0] = triangle[0][0]
        for i in xrange(1, len(triangle)):
            for j in xrange(len(triangle[i])):
                if j == 0:
                    res[i][j] = res[i-1][j] + triangle[i][j]
                elif j == len(triangle[i])-1:
                    res[i][j] = res[i-1][j-1] + triangle[i][j]
                else:
                    res[i][j] = min(res[i-1][j-1], res[i-1][j]) + triangle[i][j]
        return min(res[-1])
        
    # Modify the original triangle, top-down
    def minimumTotal2(self, triangle):
        if not triangle:
            return 
        for i in xrange(1, len(triangle)):
            for j in xrange(len(triangle[i])):
                if j == 0:
                    triangle[i][j] += triangle[i-1][j]
                elif j == len(triangle[i])-1:
                    triangle[i][j] += triangle[i-1][j-1]
                else:
                    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
        return min(triangle[-1])
        
    # Modify the original triangle, bottom-up
    def minimumTotal3(self, triangle):
        if not triangle:
            return 
        for i in xrange(len(triangle)-2, -1, -1):
            for j in xrange(len(triangle[i])):
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
        return triangle[0][0]
    
    # bottom-up, O(n) space
    def minimumTotal(self, triangle):
        if not triangle:
            return 
        res = triangle[-1]
        for i in xrange(len(triangle)-2, -1, -1):
            for j in xrange(len(triangle[i])):
                res[j] = min(res[j], res[j+1]) + triangle[i][j]
        return res[0]

  • 0
    S

    Thanks for your sharing! And I like your summary of multiple ways to solve the same problems.


  • 0
    F

    Thanks for sharing,helping me to better understand this question!


  • 0
    L

    the time complexity is O(n*n)?


  • 0
    D

    Sharing my 6-line passed solution

            height = len(triangle)
            distance = triangle[0]*height
            for h in range(1,height):
                for i in range(h,-1,-1):
                    choose_path = min(distance[max(i-1,0):min(i+1,h)])
                    distance[i] = triangle[h][i] + choose_path
            return min(distance)
            
    

  • 0

    @caikehe said in Python easy to understand solutions (top-down, bottom-up).:

    def minimumTotal2(self, triangle):
    if not triangle:
    return
    for i in xrange(1, len(triangle)):
    for j in xrange(len(triangle[i])):
    if j == 0:
    triangle[i][j] += triangle[i-1][j]
    elif j == len(triangle[i])-1:
    triangle[i][j] += triangle[i-1][j-1]
    else:
    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
    return min(triangle[-1])

    Great solution, but look forward for adding DP solution.


  • 0
    A

    In solution 4 (bottom-up, O(n) space), the last row of triangle will still be modified. We can avoid this with a little modification:

    res = list(triangle[-1])
    

Log in to reply
 

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