Triangle

LeetCode 120

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        
        """
        """
        Find the minimum path sum from top to bottom
        2 + 3 + 5 + 1 = 11
        技巧是加一層底
        [
             [2],
            [3,4],
           [6,5,7],
          [4,1,8,3]
        ]
        
        [2]
        [3,4]
        [6,5,7]
        [4,1,8,3]
        [0,0,0,0,0]
        """
        f = [0] * (len(triangle)+1)
        for row in triangle[::-1]:
            for i in range(len(row)):
                f[i] = row[i] + min(f[i], f[i+1])
        return f[0]