Question Name: Triangle
Solution to Triangle by LeetCode
# @param triangle, a list of lists of integers
# @return an integer
def minimumTotal(self, triangle):
# Empty triangle
if len(triangle) == 0: return 0
# The length of triangle is equal to the length of its last row.
pathSum =  * len(triangle)
# Initialize the pathSum with the first row
pathSum = triangle
# Compute the remaining rows
for row in xrange(1, len(triangle)):
# The last element of current row can only be reached from the
# last element of previous row.
pathSum[row] = pathSum[row-1] + triangle[row][row]
# Each element can be reached from two adjacent nodes in the
# previous row.
for column in xrange(row-1, 0, -1):
pathSum[column] = min(pathSum[column], pathSum[column-1]) +
# The first element of current row can only be reached from the
# first element of previous row.
pathSum += triangle[row]
# Return the length of the shortest path.
Great! Thanks for this new method. Mine is top-down, while yours is bottom-up.