【算法题】120. 三角形最小路径和-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
120. 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]]
输出：-10
提示：
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
2.题解
思路
我们以triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]为例
[2]
[3,4]
[6,5,7]
[4,1,8,3]
这题要求从三角形最顶层到最底层的最小路径和。
如何没有要求，我们在每一层中选出一个最小的数出来，进行累加就行了。
不过这题要求每一步只能移动到下一行中相邻的结点上。就这一句话，就显然说明了当前这步是由上一行所决定而来的。
那么具体点呢？
当前行的这一步是由它的上方或者左上方走过来的。
比如说：要想走到5这里，你必须经过3或者4。
当然，我们还需要考虑一些特殊的地方：
最顶层的一个元素和之后的每一行中首尾两个元素。
因为最顶层的上方左上方都没元素了。
而之后的每一行中的首尾两个元素的左上方没有元素了。
考虑到这些，我们用dp[i][j]来表示从三角形顶部走到位置(i,j)的最小路径和。
我们结合下方的dp图：
就很容易地可以得出状态转移方程：
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
至于这些前面谈到的特殊元素，因为它们的路径都是固定只有一个点可以到达，所以我们可以直接给它们赋上值：
dp[0][0]=triangle[0][0]
for i in range(1,n):dp[i][0]=triangle[i][0]+dp[i-1][0]dp[i][i]=triangle[i][i]+dp[i-1][i-1]
Python代码
class Solution(object):def minimumTotal(self, triangle):""":type triangle: List[List[int]]:rtype: int"""n=len(triangle)dp=[[0]*(x+1) for x in range(n)] # 初始化dp数组dp[0][0]=triangle[0][0]for i in range(1,n):dp[i][0]=triangle[i][0]+dp[i-1][0] # 将这些特殊元素直接赋上值dp[i][i]=triangle[i][i]+dp[i-1][i-1]for i in range(1,n):for j in range(1,i):dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j] # 利用状态转移方程return min(dp[n-1])
3.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。
