Question: https://oj.leetcode.com/problems/triangle/
Question Name: Triangle
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution: # @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 = [0] * len(triangle) # Initialize the pathSum with the first row pathSum[0] = triangle[0][0] # 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]) + triangle[row][column] # The first element of current row can only be reached from the # first element of previous row. pathSum[0] += triangle[row][0] # Return the length of the shortest path. return min(pathSum) |
Java solution:
Great! Thanks for this new method. Mine is top-down, while yours is bottom-up.