120.三角形最小路径和

思路：dp 数组，每次从后往前更新，头尾两个值只有一种情况，即尾只能加上上一层最末的，头只能加上上一层最前的，其余的话

dp[i]=min(dp[i - 1] + item[i], dp[i] + item[i])

class Solution(object):
    def minimumTotal(self,triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = [0] * len(triangle)
        dp[0] = triangle[0][0]
        for item in triangle[1:]:
            dp[len(item) - 1] = dp[len(item) - 2] + item[len(item) - 1]
            for i in range(len(item) - 2,0,-1):
                dp[i] = min(dp[i - 1] + item[i], dp[i] + item[i])
            dp[0] = dp[0] + item[0]
            #print(dp)
        res = min(dp)
        return res