题解 | 三角形最小路径和

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        n=len(triangle)
        dp=[0]*n
        dp[0]=triangle[0][0]
        for i in range(1,n):
            dp[i]=dp[i-1]+triangle[i][i]
            for j in range(i-1,0,-1):
                dp[j]=min(dp[j],dp[j-1])+triangle[i][j]
            dp[0]+=triangle[i][0]
        return min(dp)