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 = 2for 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 += 1return 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)

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 = tempRowreturn 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