题解 | 三角形最小路径和

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#

#1.线性dp
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        #逆向思维，自底向上
        dp=triangle[-1]
        n=len(triangle)
        for i in range(n-2,-1,-1):#从倒数第二行开始
            for j in range(len(triangle[i])): #必须正向，避免覆盖
                dp[j]=min(dp[j],dp[j+1])+triangle[i][j]
        return dp[0]

#1. 二维dp的求解思路
# class Solution:
#     def minTrace(self , triangle: List[List[int]]) -> int:
#         # write code here

#         #dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
#         dp=triangle
#         for i in range(1,len(triangle)):
#             for j in range(len(triangle[i])):                 
#                 if j==0:
#                     dp[i][j]=dp[i-1][j]+triangle[i][j]
#                 elif j==len(triangle[i])-1:
#                     dp[i][j]=dp[i-1][j-1]+triangle[i][j]
#                 else:
#                      dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]
#         return min(dp[len(triangle)-1])