LeetCode-120-三角形最小路径和

解题思路：

1. 状态转移，当前点的最小路径和=min（上一行同列，上一行前一列）的最近路径的最小值+当前点的value：dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
2. 需初始化三角形的两侧，两侧的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]