# Python easy to understand solutions (top-down, bottom-up).

• ``````# O(n*n/2) space, top-down
def minimumTotal1(self, triangle):
if not triangle:
return
res = [[0 for i in xrange(len(row))] for row in triangle]
res[0][0] = triangle[0][0]
for i in xrange(1, len(triangle)):
for j in xrange(len(triangle[i])):
if j == 0:
res[i][j] = res[i-1][j] + triangle[i][j]
elif j == len(triangle[i])-1:
res[i][j] = res[i-1][j-1] + triangle[i][j]
else:
res[i][j] = min(res[i-1][j-1], res[i-1][j]) + triangle[i][j]
return min(res[-1])

# Modify the original triangle, top-down
def minimumTotal2(self, triangle):
if not triangle:
return
for i in xrange(1, len(triangle)):
for j in xrange(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
return min(triangle[-1])

# Modify the original triangle, bottom-up
def minimumTotal3(self, triangle):
if not triangle:
return
for i in xrange(len(triangle)-2, -1, -1):
for j in xrange(len(triangle[i])):
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
return triangle[0][0]

# bottom-up, O(n) space
def minimumTotal(self, triangle):
if not triangle:
return
res = triangle[-1]
for i in xrange(len(triangle)-2, -1, -1):
for j in xrange(len(triangle[i])):
res[j] = min(res[j], res[j+1]) + triangle[i][j]
return res[0]``````

• Thanks for your sharing! And I like your summary of multiple ways to solve the same problems.

• Thanks for sharing,helping me to better understand this question!

• the time complexity is O(n*n)?

• Sharing my 6-line passed solution

``````        height = len(triangle)
distance = triangle[0]*height
for h in range(1,height):
for i in range(h,-1,-1):
choose_path = min(distance[max(i-1,0):min(i+1,h)])
distance[i] = triangle[h][i] + choose_path
return min(distance)

``````

• def minimumTotal2(self, triangle):
if not triangle:
return
for i in xrange(1, len(triangle)):
for j in xrange(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
return min(triangle[-1])

Great solution, but look forward for adding DP solution.

• In solution 4 (bottom-up, O(n) space), the last row of triangle will still be modified. We can avoid this with a little modification:

``````res = list(triangle[-1])
``````

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