Triangle

Problem: Triangle

We use a growing list to represent the dynamic programming list and update it during iterating through each row of the triangle.

Code in Python:

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = [0]
        for row in triangle:
            cur = []
            for i in xrange(len(row)):
                if i == len(row) -1:
                    cur.append(row[len(row)-1] + dp[-1])
                elif i == 0:
                    cur.append(row[0] + dp[0])
                else:
                    cur.append(row[i] + min(dp[i-1], dp[i]))
            dp[:] = cur[:]
        return min(dp)