三角形最小路径和

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

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

        return min(dp[-1])

class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # 定义dp[i][j]为从下往上到第[i,j]个元素时的最小路径和
        # 最后结果为dp[0][0]
        # dp转移方程为: dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
        # 初始状态: dp[m-1][j] = triangle[m-1][j]

        m, n = len(triangle), len(triangle[-1])
        dp = [[0 for _ in range(n)] for _ in range(m)]

        for j in range(n):
            dp[m-1][j] = triangle[m-1][j]

        for i in range(m-2, -1, -1):
            for j in range(i+1):
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
        return dp[0][0]