image.png

解題思路：

1. 狀態(tài)轉(zhuǎn)移，當(dāng)前點(diǎn)的最小路徑和=min（上一行同列，上一行前一列）的最近路徑的最小值+當(dāng)前點(diǎn)的value：dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
2. 需初始化三角形的兩側(cè)，兩側(cè)的dp值由路徑上的triangle累加即可；
3. 也可以自底向上遍歷。
   Python3代碼

# 自頂向下遍歷
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [[0]*len(triangle[i]) for i in range(len(triangle))]
        dp[0][0]= triangle[0][0]
        for i in range(1, len(triangle)):
            dp[i][0] = triangle[i][0] + dp[i-1][0]
            dp[i][-1] = triangle[i][-1] + dp[i-1][-1]
        for i in range(1, len(triangle)):
            for j in range(1, len(triangle[i])-1):
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
        return min(dp[-1])

# 自底向上遍歷
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [[0]*len(triangle[i]) for i in range(len(triangle))]
        dp[-1]=triangle[-1]
        for i in range(len(triangle)-2, -1, -1):
            for j in range(0, i+1):
                dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
        return dp[0][0]