Fast iterative dp python code 56ms and only uses O(n) space


  • 0
    D

    This is a simple dynamic programming idea: result[i][j] = triangle[i][j] + min(result[i-1][j-1], result[i-1][j]). I just simplify the array to one dimension and update it in every loop.

    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)
        if n == 0: return 0
        result = [2147483647 for x in range(n)]
        result[0] = triangle[0][0]
        for i in range(1, n):
            temp = 2147483647
            for j in range(i + 1):
                temp1 = result[j]
                result[j] = triangle[i][j] + min(temp, result[j])
                temp = temp1
        return min(result)

Log in to reply
 

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