题解 | #三角形最小路径和#

• 利用一个数组dp来存储当前层的上一层元素，然后从前往后修改dp数组中的元素。
• dp[j] = triangle[i][j] + min(dp[j],dp[j+1])，其中j表示当前层的第j个元素的下标。
• 通过从后往前遍历每一层，就找到了每一个点的最小值的路径，最终遍历至一底层，最小值存储在dp[0]

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