本文共 761 字，大约阅读时间需要 2 分钟。

题目

基本思路

这是典型的动态规划问题

[  [2],  [3,4],  [6,5,7],  [4,1,8,3]]

最后一行的元素就作为我们的dp数组，从倒数第二行的第一个元素6开始，6可以和下一行的，4，1两个数字进行相加，同时可以发现可以和他相加的这两个数字的坐标一个和6相同，一个比6的坐标大1，所以我们得出公式：

// 一般动态规划问题，公式出来了就已经全部解决了。dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

这个相加过程可以具体理解为

// 请从下往上观看  [11,10,10,3]  [9,10,10,3]  [7,6,10,3]  [4,1,8,3]

实现代码

class Solution:    def minimumTotal(self, triangle):        """        :type triangle: List[List[int]]        :rtype: int        """        # 从后往前使用动态规划        length = len(triangle)        if length == 0:            return 0        dp = triangle[-1]        for i in range(length-2,-1,-1):            for j in range(i+1):                dp[j] = triangle[i][j] + min(dp[j],dp[j+1])        return dp[0]