# 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 = [ * (i+1) for i in range(let)]        dp = triangle        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`

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