# Accepted solution in Python

• The code is based on dynamic programming. Let me know if you have any comments on improving it.

``````class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
mintmp=[0]*len(triangle)
mintmp[0]=triangle[0][0] # initialized for the first layer
for i in range (1,len(triangle)):
mintmp[i]=mintmp[i-1]+triangle[i][i] # update the largest note
for j in range(i-1,0,-1): # reversely update all the notes
mintmp[j]=min(mintmp[j-1],mintmp[j])+triangle[i][j]
mintmp[0]=mintmp[0]+triangle[i][0] # update the lowest one
return min(mintmp)``````

• DP in place solution, bottom up direction, updates nodes by adding minimum of two underlying nodes

``````class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
for level in range(1, len(triangle))[::-1]:
for i in range(0, len(triangle[level]) - 1):
triangle[level-1][i] += min(triangle[level][i], triangle[level][i+1])

return triangle[0][0]
``````

DP with O(n) extra space, if no changes in original triangle allowed, the same idea, using temporary array to store calculated minimal sums

``````class Solution:
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
tmp = triangle[len(triangle) - 1]
for level in range(1, len(triangle))[::-1]:
for i in range(0, len(triangle[level]) - 1):
tmp [i] = triangle[level-1][i] + min(tmp[i], tmp[i+1])

return tmp[0]
``````

• Thanks radovan! Your solution that use triangle itself to store the intermediate minimum sum is great! Also bottom up is a super awesome idea! No boundary problem and the need to calculate the minimum value. Thanks for sharing!

IMHO, if later the path need to be determined, I am afraid, the code need to have additional space and calculate from top to bottom.

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