120. Triangle

Approach 1: Storing row sums using DP

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        let = len(triangle)
        dp = [[0] * (i+1) for i in range(let)]
        dp[0][0] = triangle[0][0]
        counter = 2
        for i in range(1, let):
            for j in range(counter):
                if j == 0:
                    dp[i][j] = triangle[i][j] + dp[i-1][j]
                elif j == counter - 1:
                    dp[i][j] = triangle[i][j] + dp[i-1][j-1]
                else:
                    dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
            counter += 1
        return min(dp[-1])

As like a standard DP problem, we will store the sums up to the previous row and use it to update the next row. The update condition here being: dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]) where (i,j) are the current co-ordinates of the triangle matrix for which the min sum is being evaluated, and dp[i][j] stores the sums up to row i and location j.

d[element] = element + min(d[left_parent], d[right_parent])

Time Complexity: O(N), where N is the total number of numbers in triangle

Space Complexity: O(N)

Approach 1: Same as above but O(1) space

In the above solution it is visible that the for row N we only need information from row N-1 and so on. This way we can optimize memory as below

class Solution(object):
    def minimumTotal(self, triangle):
        """
        https://leetcode.com/problems/triangle/description/
        :type triangle: List[List[int]]
        :rtype: int
        """
        lastRow = triangle[-1]

        for row in reversed(triangle[:-1]):
            tempRow = row[:]
            for i in range(0,len(row)):
                tempRow[i] += min(lastRow[i], lastRow[i+1])
            lastRow = tempRow
        return lastRow[0]

Time Complexity: O(N), where N is the total number of numbers in triangle

Space Complexity: O(n), where n is the number of rows. N = n(n+1)/2