动态规划, 使用两个数组, dp记录当前行信息, oldDp记录上一行信息。dp[i]的含义是从顶端走到当前行dp[i]这个位置的最小路径和。

class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        length = len(triangle)
        dp = [0 for i in xrange(length)]
        for row in triangle:
            oldDp = dp[:]
            for i in xrange(len(row)):
                if i == 0: 
                    dp[i] = oldDp[i] + row[i]
                elif i == len(row) - 1:
                    dp[i] = oldDp[i-1] + row[i]
                else:
                    dp[i] = min(oldDp[i], oldDp[i-1]) + row[i]
        return min(dp)