Triangle

这题主要是空间优化后的循环需要注意一下

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)
        dp = [0] * n
        dp[0] = triangle[0][0]

        for i in xrange(1, n):
            for j in xrange(i, -1, -1):
                if 0 < j < i:
                    dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]
                elif j == 0:
                    dp[j] += triangle[i][j]
                else:
                    dp[j] = dp[j - 1] + triangle[i][j]
        return min(dp)