My python solution, easy to understand with explaination


  • 1
    C

    from the second layer, update the layer number every time.
    from example.the following.

        [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    

    the first layer is 2. update the second the second layer [3+2, 4+2] = [ 5, 6]. then update the third layer
    [6+5, 5+min(5, 6), 7+6] = [11, 10, 13], then the forth layer is [4+11,1+min(11, 10), 8 + min(5, 7), 3+7] = [15, 11, 13, 10], then the result is 11.
    the code is like this:

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

Log in to reply
 

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