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


  • 0
    C

    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
                    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.