A top-bottom python solution with O(n) space

  • 0

    You can do it from top to bottom using a O(n) space too.

        def minimumTotal(self, triangle):
            :type triangle: List[List[int]]
            :rtype: int
            if not triangle: return 0
            dp = [0] * len(triangle)
            temp = []
            for i in range(len(triangle)):
                temp[:] = dp # you can't use temp=dp here
                for j in range(0,i+1):
                    # edge cases
                    if j == 0:
                        dp[j] = temp[j] + triangle[i][0]
                    elif j == i:
                        dp[j] = temp[j-1] + triangle[i][i]
                    # else
                        dp[j] = min(temp[j-1], temp[j]) + triangle[i][j]
            return min(dp)

    It's slower than bottom-top solution, because you need to duplicate dp every iteration.

    OK, it's O(2n) space, I have to admit.:)

Log in to reply

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