120. Triangle

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        #work from bottom up 
        if not triangle:
            return 0
        
        n=len(triangle)
        dp=triangle[n-1]
        for i in reversed(xrange(n-1)):
            for j in xrange(i+1):
                dp[j]=min(dp[j],dp[j+1])+triangle[i][j]
                
        return dp[0]