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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#
import copy
class Solution:
    def minTrace(self , triangle: list[list[int]]) -> int:
        # write code here


    #简历原来数组的dp数组并初始化。
        dp = copy.deepcopy(triangle)
        for i in range(len(dp)):
            for j in range(len(dp[i])):
                dp[i][j]=0

        n=len(dp)
        for i in range(n):
            for j in range(len(dp[i])):
                if i==0 and j==0:
                    dp[i][j]=triangle[i][j]

                elif j==0:
                   dp[i][j]=dp[i-1][j]+triangle[i][j]

                elif j==len(dp[i])-1:
                    dp[i][j]=dp[i-1][j-1]+triangle[i][j]



                elif n>i>0 and len(dp[i])>j>0:
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]

        mindp=10000000000000000
        for i in range(len(dp[n-1])):
            mindp=min(mindp,dp[n-1][i])
        return mindp