一、题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2
输入：triangle = [[-10]]
输出：-10
提示：1 <= triangle.length <= 200triangle[0].length == 1 triangle[i].length == triangle[i - 1].length + 1-10^4 <= triangle[i][j] <= 10^4
二、代码
代码如下：
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
for row in range(1,len(triangle)):
print(f"row = {row} 时，当前行的长度为：",len(triangle[row]))
for col in range(len(triangle[row])):
if col > 0 and col < len(triangle[row])-1 : #当前位置非边界处，有2种情况
path = [e+triangle[row][col] for e in triangle[row-1][col-1:col+1]]
if col == 0: #当前位置在当前行最左边 ， 只有一种情况
path = [triangle[row-1][col] + triangle[row][col]]
if col == len(triangle[row])-1 :#当前位置在当前行最右边 ， 只有一种情况
path = [triangle[row - 1][-1] + triangle[row][col]]
print("path:",path)
# 在path中选择最小的一个值，作为当前位置的值
triangle[row][col] = min(path)
print(triangle)
print(min(triangle[-1]))
return min(triangle[-1])
三、解题思路
本题是寻找自顶向下三角形最小路径和，其规则类似于二叉树，当前节点只能由其相邻的父结点下来。
本题解最容易想到的思路是把所有路径都遍历一遍的方法，即采用回溯方法把每一条可能的路径都计算出总和，最后选择最小值返回即可。但是该方法的问题是，并不能满足输入序列非常大的时候，并且回溯方法耗费时间，容易导致“超出时间限制”的问题。
故本题解寻求该三角形数组的规律，具体思路是计算每层中每一个元素对应的最小路径总和，然后层层递进，直到计算到三角形最后一层结束。最终所需要寻求的结果从三角形最后一层中找到最小值即可。
以triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]为例：
2
3 4
6 5 7
4 1 8 3
我们从三角形第二层（即row = 1）开始计算，计算该层每一个元素当前对应的最短路径总和，因为第二层中每一个元素只可能从第一层中唯一一个元素走下来，所以当前层每一个元素对应的最短路径和应该为：[3, 4]->[3+2, 4+2]->[5, 6]，用[5, 6]替换原本的数据，用于第三层的计算。
2
3+2 4+2
6 5 7
4 1 8 3
然后计算第三层每一个元素对应的最短路径总和，这里出现了新情况，就是有元素（位于中间位置的5）存在不同路径的总和（即[5+5 or 6+5]->[10 or 11]），此时我们秉承着找最小路径的原则，选择最小的值（即从左边下来的路径5+5，求得10）来作为当前的位置的最小路径和。最后得到[11, 10, 13]，用与第四层的计算。
2
5 6
6+5 5+5 7+6
4 1 8 3
同理，最后一层中的计算方法也同第三层一样，在第四层中，存在有多个（1和8）不同路径的元素点，我们还是取其对应最小值即可，最后结果为[15, 11, 18, 16]:文章来源：https://www.toymoban.com/news/detail-421420.html
2
5 6
11 10 13
4+11 1+10 8+10 3+13
我们所需要求的结果，就是最后一层中的最小值，即11，返回即可。
以上便是寻求规律所得题解。文章来源地址https://www.toymoban.com/news/detail-421420.html
到了这里，关于120. 三角形最小路径和 Python的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
