O(n) space python dp solution


  • 0
    C
    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
            #sum of all elements
            n = len(triangle)
            dp = [[0]*n for i in range(2)]
            dp[0][0] = triangle[0][0]
            for i in range(1,n):
                i1 = i & 1 #current row
                i0 = (i+1) & 1 # last row
                dp[i1][0] = dp[i0][0] + triangle[i][0]
                dp[i1][i] = dp[i0][i-1] + triangle[i][i]
                for j in range(1,i):
                    dp[i1][j] = min(dp[i0][j-1],dp[i0][j])+triangle[i][j]
            return min(dp[(n-1)&1])
    

Log in to reply
 

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