120. 三角形最小路径和

一、120. 三角形最小路径和 1.1、题目描述

初看，和64.最小路径和有点相似，但是本题的结束位置并不是右下角。

1.2.1、动态规划

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        m = len(triangle)
        mini = [0] * m
        mini = triangle[-1]
        for i in range(m-2, -1, -1):
            for j in range(len(triangle[i])):
                mini[j] = triangle[i][j] + min(mini[j], mini[j+1])
        return mini[0]
                

二、931. 下降路径最小和 2.1、题目描述

2.2.1、动态规划

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        m,n = len(A), len(A[0])
        
        for i in range(1, m):
            for j in range(n):
                _min = A[i-1][j]
                if j >= 1:
                    _min = min(_min, A[i-1][j-1])
                if j