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

  • 5
    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

    Change the reversed, you will save some extra time.

  • 0

    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.