打卡群刷题总结0816——三角形最小路径和

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0 or len(triangle[-1]) == 0:
            return 0

        dp = [0] * len(triangle[-1])
        dp[0] = triangle[0][0]
        for i in range(1, len(triangle)):
            length = len(triangle[i])
            dp[length - 1] = dp[length - 2] + triangle[i][length - 1]
            for j in range(length - 2, 0, -1):
                dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]
            dp[0] += triangle[i][0]
        return min(dp)