Triangle

Question

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Notice: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Thoughts

Use Dynamic Programming algorithm. The memo is a list with length of n (n is the height of the triangle). Start from the top of the triangle and traverse to the bottom of the triangle.

In the recurrence equation, there are three situation:

1. The item is at the beginning of the line: result[j] = result[j] + triangle[i][j]
2. The item is at the end of the line: result[j] = result[j - 1] + triangle[i][j]
3. Other situation: result[j] = min(result[j - 1], result[j]) + triangle[i][j]

Code

class Solution:
    """
    @param triangle: a list of lists of integers.
    @return: An integer, minimum path sum.
    """
    def minimumTotal(self, triangle):
        # write your code here
        result = [0 for i in xrange(len(triangle))]
        result[0] = triangle[0][0]
        for i in xrange(1, len(triangle)):
            tmp = list(result[:i])
            for j in xrange(i + 1):
                if j == 0:
                    result[j] = tmp[j] + triangle[i][j]
                elif j == i:
                    result[j] = tmp[j - 1] + triangle[i][j]
                else:
                    result[j] = min(tmp[j - 1], tmp[j]) + triangle[i][j]
        return min(result)