120. 三角形最小路径和

https://leetcode-cn.com/problems/triangle/

解法一：dp

用一个一维dp数组，自底向上迭代即可。dp初始为三角形倒数第一行，从倒数第二行开始迭代。dp[j]的新值为相邻位置较小值加上当前位置三角形的值

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1]
        for i in range(len(triangle)-2, -1, -1):    #自底向上，对三角形的每行
            for j in range(len(triangle[i])):    #从左到右，对三角形该行的每个位置
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        return dp[0]