My 4-line python solution with O(1) space


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

    It's a bottom-up dp, and direct modify the input array instead of using an extra array


  • 0
    H

    Change the reversed, you will save some extra time.


  • 0
    Z

    I like your code, clean, and easily translated to other language


Log in to reply
 

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